#include "bits/stdc++.h"
using namespace std;
using ll = long long;


void work(){
    ll n,k;cin>>n>>k;

    vector<tuple<ll,ll,ll> > vc(n);
    for(auto &[u,v,w]:vc)cin>>u>>v>>w;

    sort(vc.begin(),vc.end(),[](tuple<ll,ll,ll> a,tuple<ll,ll,ll> b){
        return get<2>(a)>get<2>(b);
    });


    ll ans = 0;
    ll sheng = 0;
    ll yy = 0;
    for(int i = 0; i < n ;){
        auto &[c,w,h] = vc[i];

        if(c==0){
            ++i;
            continue;
        }


        if(w&1&&yy&&c){
            int tem = min(c,yy);
            c -= tem;
            yy -= tem;
            continue;
        }
        if(c/(k/w)){
            ll nc = c%(k/w);
            ans += c/(k/w)*h;
            c = nc;
            continue;
        }


        if(sheng==0){
            sheng = k;
            ans += h;
        }

        if(w&1){
            int tem = min(c,sheng);
            c -= tem;
            sheng -= tem;
        }else{
            if(sheng==1){
                yy++;
                continue;
            }
            int tem = min(c,sheng/2);
            c-=tem;
            sheng -= tem*2;
        }
    }

    cout<<ans<<'\n';


}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while (t--){
        work();
    }
    return 0;
}