#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});
    for(auto [u,v]:v1){
        v2.push_back({u,v/2});
        if(v&1) vx.push_back(u);
    }
    sort(vx.begin(),vx.end());
    while(vx.size()){
        v2.push_back({vx.back(),1});
        vx.pop_back();
        if(vx.size()) vx.pop_back();
    }
    sort(v2.begin(),v2.end(),greater<PII>());
    ll ans=0;
    int i=0;
    m/=2;
    while(i<v2.size()){
        ll cnt=v2[i].second/m;
        ans+=cnt*v2[i].first;
        v2[i].second%=m;
        if(v2[i].second==0){
            v2.pop_back();
            continue;
        }
        ll need=m;
        ans+=v2[i].first;
        while(i<v2.size()&&need>=v2[i].second){
            need-=v2[i].second;
            i++;
        }
        if(i<v2.size())
        v2[i].second-=need;
    }
    printf("%lld\n",ans);
}

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