#include<bits/stdc++.h>
using namespace std;
const int V = 5010;
const int E = 100100;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k,p;

void __(){
    scanf("%lld%lld",&n,&m);
    map<ll,ll> mp1,mp2;
    for(int i=1;i<=n;i++){
        int c,w,f;
        scanf("%d%d%d",&c,&w,&f);
        if(w==1) mp1[f]+=c;
        else mp2[f]+=c;
    }
    vector<PII> v1,v2;
    vector<int> vx;
    for(auto [u,v]:mp1) v1.push_back({u,v});
    for(auto [u,v]:mp2) v2.push_back({u,v});
   
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    ll ans=0;
    while(v1.size()&&v2.size()){
        auto u=v1.back(),v=v2.back();
        if(u.first<=v.first){
            ll cnt=m/2;
            ans+=v2.back().second/cnt*v2.back().first;
            v2.back().second%=cnt;
        }else{
            ll cnt=m;
            ans+=v1.back().second/cnt*v1.back().first;
            v1.back().second%=cnt;
        }
        ll need=m;
        ll res=0;
        while(v1.size()&&v2.size()){
            auto &u=v1.back(),&v=v2.back();
            if(need>=2&&u.first<=v.first){
                if(v.second*2<=need){
                    need-=v.second*2;
                    ans=max(ans,v.first);
                    v2.pop_back();
                }else{
                    v.second-=need/2;
                    need%=2;
                    ans=max(ans,v.first);
                }
            }else{
               if(u.second<=need){
                    need-=u.second;
                    ans=max(ans,u.first);
                    v1.pop_back();
                }else{
                    u.second-=need;
                    need=0;
                    ans=max(ans,u.first);
                }
            }
        }
        while(need>1&&v2.size()){
            auto &v=v2.back();
            if(v.second*2<=need){
                    need-=v.second*2;
                    ans=max(ans,v.first);
                    v2.pop_back();
                }else{
                    v.second-=need/2;
                    need%=2;
                    ans=max(ans,v.first);
                }
        }
        while(need>0&&v1.size()){
            if(u.second<=need){
                    need-=u.second;
                    ans=max(ans,u.first);
                    v1.pop_back();
                }else{
                    u.second-=need;
                    need=0;
                    ans=max(ans,u.first);
                }
        }
    }
    while(v2.size()){
        ans+=v2.back().first;
        ll need=m;
        while(need>1&&v2.size()){
            auto &v=v2.back();
            if(v.second*2<=need){
                    need-=v.second*2;
                    ans=max(ans,v.first);
                    v2.pop_back();
                }else{
                    v.second-=need/2;
                    need%=2;
                    ans=max(ans,v.first);
                }
        }
    }
    while(v1.size()){
        ans+=v1.back().first;
        ll need=m;
        while(need>0&&v1.size()){
            auto &u=v1.back();
            if(u.second<=need){
                    need-=u.second;
                    ans=max(ans,u.first);
                    v1.pop_back();
                }else{
                    u.second-=need;
                    need=0;
                    ans=max(ans,u.first);
                }
        }
    }
    printf("%lld\n",ans);
}

int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
    
}