#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct CuocHop {
    int batDau, ketThuc, chiPhi;
};

// Hàm so sánh để sắp theo thời gian kết thúc (dùng cho greedy)
bool soSanhKetThuc(const CuocHop &a, const CuocHop &b) {
    return a.ketThuc < b.ketThuc;
}

// Tìm cuộc họp gần nhất không trùng thời gian (kết thúc <= bắt đầu hiện tại)
int timCuocHopTruoc(const vector<CuocHop>& ds, int i) {
    int l = 0, r = i - 1, kq = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (ds[m].ketThuc <= ds[i].batDau) {
            kq = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return kq;
}

int main() {
    vector<CuocHop> ds = {
        {1, 3, 50},
        {3, 5, 20},
        {0, 6, 100},
        {5, 7, 30},
        {5, 9, 60},
        {7, 8, 25},
        {8, 11, 55},
        {2, 13, 75}
    };

    int n = ds.size();

    // ======= Câu 1: Tối đa số lượng cuộc họp (Greedy) =======
    sort(ds.begin(), ds.end(), soSanhKetThuc);

    int dem = 0, ketThucGanNhat = -1;

    for (const auto &hop : ds) {
        if (hop.batDau >= ketThucGanNhat) {
            dem++;
            ketThucGanNhat = hop.ketThuc;
        }
    }

    cout << "1. So cuoc hop nhieu nhat co the to chuc la: " << dem << endl;

    // ======= Câu 2: Tối đa tổng chi phí thu được (Quy hoạch động) =======
    vector<int> dp(n, 0);

    dp[0] = ds[0].chiPhi;

    for (int i = 1; i < n; i++) {
        int chon = ds[i].chiPhi;
        int truoc = timCuocHopTruoc(ds, i);
        if (truoc != -1)
            chon += dp[truoc];

        dp[i] = max(dp[i - 1], chon);
    }

    cout << "2. Tong tien thu nhieu nhat co the dat duoc la: " << dp[n - 1] << endl;

    return 0;
}