ICECREM

#include<bits/stdc++.h>

using namespace std;

const int MX = (1<<18);

int T;

struct item{
    int P , W , V;
    item(){}
};

int main(){

    cin>>T;

    while(T--){

        int n; cin>>n;

        vector < item > v;

        for(int j = 1 ; j <= n ; j++){
            item x;
            cin>>x.W>>x.P>>x.V;
            v.push_back(x);
        }


        if(n == 1){
            cout<<v[0].V<<endl;
            continue;
        }

        vector < item > v1 , v2;

        for(int j = 0 ; j < n/2 ; j++) v1.push_back(v[j]);

        for(int j = n/2 ; j < n ; j++) v2.push_back(v[j]);

        vector < pair < long long , long long > > vec;

        for(int mask = 0 ; mask < (1<<(int)(v1.size())) ; mask++){
            long long curT = 0 , curV = 0;
            bool ok = 1;
            for(int j = 0 ; ok && j < v1.size() ; j++){
                if( (mask & (1<<j)) == 0 ) continue;
                if(curT > v1[j].W)
                    ok = 0;
                curT += v1[j].P;
                curV += v1[j].V;
            }
            if(!ok) continue;
            vec.push_back({curT , -curV});
        }

        sort(vec.begin() , vec.end());

        vector < pair < long long , long long > > ph;

        for(auto &pp : vec){
            pp.second *= -1;
            if(ph.empty()){
                ph.push_back(pp);
            }
            else{
                if(ph.back().second < pp.second)
                    ph.push_back(pp);
            }

        }

        long long ans = 0;

        for(int mask = 0 ; mask < (1<<( (int) (v2.size()))) ; mask++){
            long long curT = 0 , curV = 0 , f = (1ll << 33);
            bool ok = 1;
            for(int j = 0 ; ok && j < v2.size() ; j++){
                if( (mask & (1<<j)) == 0 ) continue;
                if(curT > v2[j].W)
                    ok = 0;
                f = min(f , 1ll * v2[j].W - curT);

                curT += v2[j].P;
                curV += v2[j].V;
            }
            if(!ok) continue;
            auto ind = upper_bound(ph.begin() , ph.end() , make_pair(f , (1ll << 62))) - ph.begin();
            --ind;
            ans = max(ans , curV + ph[ind].second);
        }


        cout<<ans<<endl;


    }





}