https://pintia.cn/problem-sets/1813039306479005696/exam/problems/type/7?problemSetProblemId=1813039385617129476&page=0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define int long long
#define INF 0x3f3f3f3f
#define endl '\n'
#define N 200010
const int mod = 1e9 + 7;

ll lowbit(ll x) {
    return -x & x;
}

int p[N], si[N];
int find(int x) {
    if (x == p[x])return p[x];
    p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);

struct aa {
    int t, d, p;
};
int n;
int dp[10000];

bool cmp(aa a, aa b) {
    return a.d < b.d;
}

void solve() {
    cin >> n;

    vector<aa> a;
    for (int i = 1; i <= n; i++) {
        int t, d, p;
        cin >> t >> d >> p;

        a.push_back({t, d, p});
    }

    sort(a.begin(), a.end(), cmp);


    for (int i = 0; i <= 5010; i++)dp[i] = 0;

    for (auto [t, d, p] : a) {
        for (int i = d; i >= t; i --) {
            dp[i] = max(dp[i], dp[i - t] + p);
        }
    }

    int res = 0;
    for (int i = 1; i <= 5000; i ++)res = max(res, dp[i]);

    cout << res << endl;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T --)

        solve();

    return 0;
}