#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mp make_pair
#define fr first
#define sc second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep_(_1,_2,_3,NAME,...) NAME
#define rep(...) rep_(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define rep1(i,j) for(int i=0;i<(j);i++)
#define rep2(i,j,k) for(int i=(j);i<(k);i++)

template<class T> T T_INF(){ return 1000000000000000000; }
template<> int T_INF<int>(){ return 1000000000; }

ll n,k;
ll c[300010],w[300010],f[300010];

void solve(){
    vector<pair<ll,ll>> v[2];
    rep(i,n){
        v[w[i]-1].push_back(mp(f[i],c[i]));
    }
    vector<pair<ll,ll>> a;
    sort(v[0].begin(),v[0].end(),greater<pair<ll,ll>>());
    {
        bool odd=false;
        for(auto p: v[0]){
            if(odd)p.sc--;
            if(p.sc>0)a.push_back(mp(p.fr,(p.sc+1)/2));
            odd=p.sc%2==1;
        }
    }
    sort(v[1].begin(),v[1].end(),greater<pair<ll,ll>>());
    for(auto p: v[1])a.push_back(p);
    sort(a.begin(),a.end(),greater<pair<ll,ll>>());
    
    k/=2;
    ll ret=0;
    ll z=0;
    for(auto p: a){
        if(p.sc<=z){
            z-=p.sc;
        }
        else {
            p.sc-=z;
            ll temp=(p.sc+k-1)/k;
            ret+=temp*p.fr;
            z=temp*k-p.sc;
        }
    }
    cout<<ret<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.precision(20);
    
    int T;
    cin>>T;
    rep(t,T){
        cin>>n>>k;
        rep(i,n)cin>>c[i]>>w[i]>>f[i];
        solve();
    }
}