Computer Purchase Return

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int t, n; cin >> t >> n;
    10    vector<vector<pair<int, int>>> group(t + 1);
    11    for (int i = 0; i < n; i++) {
    12        int c, v, tt; cin >> c >> v >> tt;
    13        group[tt].emplace_back(c, v);
    14    }
    15    int b; cin >> b;
    16    for (int i = 1; i <= t; i++) {
    17        if (group[i].empty()) {
    18            cout << -1 << '\n';
    19            return 0;
    20        }
    21    }
    22    vector<int> old(b + 1, -inf);
    23    old[0] = 0;
    24    for (int i = 1; i <= t; i++) {
    25        vector<int> cur(b + 1, -inf);
    26        for (auto[c, v] : group[i]) {
    27            for (int j = c; j <= b; j++) {
    28                if (old[j - c] == -inf) continue;
    29                cur[j] = max(cur[j], old[j - c] + v);
    30            }
    31        }
    32        swap(old, cur);
    33    }
    34    int ans = *max_element(old.begin(), old.end());
    35    cout << (ans < 0 ? -1 : ans) << '\n';
    36    return 0;
    37}