#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void solve(){
    int n;ll k;
    cin>>n>>k;k/=2;bool lst=0;
    vector<pair<int,int>> d[2];
    for(int i=1,x,y,z;i<=n;i++) cin>>x>>y>>z,d[y-1].emplace_back(x,z);
    sort(d[0].begin(),d[0].end(),[&](auto x,auto y){return x.second>y.second;});
    for(auto [x,y]:d[0]) d[1].emplace_back(x-lst+1>>1,y),lst^=x&1;
    sort(d[1].begin(),d[1].end(),[&](auto x,auto y){return x.second>y.second;});
    ll res=0,ans=0;
    for(auto [x,y]:d[1]) if(x){
        if(x>=res)
        res=x-res,ans+=(res+k-1)/k*1ll*y,res=(k-res%k)%k;
        else res-=x;
    }
    cout<<ans<<'\n';
}
int main(){
    int zhuzhu=1;
    cin>>zhuzhu;
    while(zhuzhu--) solve();
}