Code

#include<bits/stdc++.h>

using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define TIME cerr<<"Time Taken:"<<(float)clock()/CLOCKS_PER_SEC*1000<<"ms"<<endl

typedef long long int lli;


lli dp[2001][4002];
lli suffixSum[2001];
// tt is the sum of a[i][0] of all bombs that will give us bad luck
// im simple tt is time we are left with.
// for the ith bomb we can explode it or keep it
// if keep it then tt=tt+a[i][0]
// if we destroy it then tt=tt-1 as it takes 1 sec to destroy a bomb
// if at any point tt>=n then we can explode all the bombs from i to n-1 (indexing starts from 0)
// hence returing suffixsum of a[i][1] at line 73
// thus tt>=-n && tt<=n hence dp will be of size n * (2n)
lli f(auto &a,lli i,lli tt)
{
    lli n=a.size();
    if(i==a.size())
    {
        if(tt>=0)
            return 0;
        return -1e18;
    }
    if(tt>=n)
        return suffixSum[i];
    lli &ans=dp[i][tt+n];
    if(ans!=-1)
        return ans;
    lli x=f(a,i+1,tt+a[i][0]);
    lli y=f(a,i+1,tt-1)+a[i][1];
    if(y<0)
        y=-1e18;
    return ans=max(x,y);
}
int main() {
fastio();
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
#endif
    lli t=1,testcases=1;
    cin>>t;
    while(t>=testcases)
    {
        memset(dp,-1,sizeof(dp));
        lli n;
        cin>>n;
        vector<vector<lli>> a(n,vector<lli>(2));
        for(lli i=0;i<n;i++)
            for(lli j=0;j<2;j++)
                cin>>a[i][j];
        suffixSum[n-1]=a[n-1][1];
        for(lli i=n-2;i>=0;i--)
            suffixSum[i]=suffixSum[i+1]+a[i][1];
        cout<<f(a,0,0)<<endl;
        //cout<<"Case #"<<testcases<<": "<<ans<<endl;
        testcases++;
    }
    TIME;
    return 0;
}