因为涉及到三个变量，还需要排序，所以可以用结构体存储每个工作需要的时间、截止时间和报酬。因为越早截止的任务越早完成越好，所以我们按照截止时间从小到大进行排序。

（证明越早完成越好？）

因为每个工作都可以选择做和不做，不同的选择对后续工作的影响也不同，所以就将这个问题转换成了背包问题。

用f[i][j]表示从前i个工作中选择，在时间j时得到报酬的最大值，因为截止时间最大是5000，所以第二维只需要枚举到5000。可以得到转移方程：不完成第i个任务时：f[i][j]=f[i-1][j]，完成第i个任务时，需要当前时间在截止时间前，并且当前时间减去任务所需时间要大于等于0，若都合法则可转移：f[i][j]=max(f[i][j],f[i-1][j - a[i].t] + a[i].p)。

受到内存影响，所以无法开f[5001][5001]的数组，所以我们要改为滚动数组f[2][5001]，在每次转移后都需要使f[0][i]=f[1][i]。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fios ofstream("test.txt");cout.rdbuf(out.rdbuf())
#define INF 0x3f3f3f3f
#define MINF 2147483647
#define eps 1e-6
#define PI acos(-1)
#define lowbit(x) (x & (-x))
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 5010;

int n;
struct Node
{
    int t, d, p;

    bool operator< (const struct Node &_)
    {
        return d < _.d;
    }
}node[N];
int f[2][N];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;

        memset(f, 0, sizeof f);

        for(int i = 1; i <= n; i++)
            cin >> node[i].t >> node[i].d >> node[i].p;

        sort(node + 1, node + n + 1);

        for(int i = 1; i <= n; i++)
        {
            //cout << " == " << i << endl;
            for(int j = 1; j <= 5000; j++)
            {
                //cout << j << endl;
                f[i & 1][j] = f[(i - 1) & 1][j];
                if(j <= node[i].d && node[i].t <= j)
                    f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - node[i].t] + node[i].p);
            }
        }

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

        cout << res << endl;
    }

    return 0;
}