#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ll long long
#define lowbit(x) x&-x
const int N=1e7+1,mod=1e9+19;
void solve(){
    int n,k;cin>>n>>k;
    vector<pair<int,int>>a,b;
    map<int,int>one,two;
    for(int i=0;i<n;i++){
        int c,w,f;cin>>c>>w>>f;
        if(w==1){
            one[f]+=c;
        }else two[f]+=c;
        // if(w==1)a.emplace_back(c,f);
        // else b.emplace_back(c,f);
    }
    for(auto &[f,c]:one)a.emplace_back(c,f);
    for(auto &[f,c]:two)b.emplace_back(c,f);
    function<bool(pair<int,int>,pair<int,int>)>cmp=[&](const auto x,const auto y){
        return x.second>y.second;
    };
    sort(a.begin(),a.end(),cmp);
    sort(b.begin(),b.end(),cmp);
    ll ans=0;
    int p=k,cnt=0,ex=0;
    int l=0,li=0;
    while(l<a.size()||li<b.size()){
        if(l<a.size()&&li<b.size()){
            if(a[l].second>b[li].second){
                if(a[l].first<=ex){
                    ex-=a[l].first,a[l].first=0;
                    continue;
                }else a[l].first-=ex,ex=0;
                if(p==k){
                    cnt=a[l].second;
                }
                if(a[l].first>=k){
                    ans+=1ll*a[l].first/k*a[l].second;
                    a[l].first=a[l].first%k;
                }
                if(p>=a[l].first)p-=a[l].first;
                else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
                l++;
            }else {
                if(p==k){
                    cnt=b[li].second;
                }
                if(p==1){
                    ans+=cnt;
                    p=k;
                    ex++;
                    continue;
                }
                if(b[li].first>=k/2){
                    ans+=1l*b[li].first/(k/2)*b[li].second;
                    b[li].first=b[li].first%(k/2);
                }
                if(p>=b[li].first*2)p-=b[li].first*2;
                else{
                    if(p&1)ex++;
                    p=b[li].first*2-p,ans+=cnt;
                    if(p!=k)cnt=b[li].second;
                }li++;
            }
        }else if(l<a.size()){
                if(a[l].first<=ex){
                    ex-=a[l].first,a[l].first=0;
                    continue;
                }else a[l].first-=ex,ex=0;
                if(p==k){
                    cnt=a[l].second;
                }
                if(a[l].first>=k){
                    ans+=1ll*a[l].first/k*a[l].second;
                    a[l].first=a[l].first%k;
                }
                if(p>=a[l].first)p-=a[l].first;
                else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
                l++;
        }else {
                if(p==k){
                    cnt=b[li].second;
                }
                if(p==1){
                    ans+=cnt;
                    p=k;
                    ex++;
                    continue;
                }
                if(b[li].first>=k/2){
                    ans+=1ll*b[li].first/(k/2)*b[li].second;
                    b[li].first=b[li].first%(k/2);
                }
                if(p>=b[li].first*2)p-=b[li].first*2;
                else {
                    if(p&1)ex++;
                    p=b[li].first*2-p,ans+=cnt,cnt=b[li].second;
                }
                li++;
        }
        if(p==0){
            p=k;ans+=cnt;
        }
    }
    if(p!=k)ans+=cnt;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}