#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=1e5+5;
int read(){
	int x=0,f=1; char c=getchar();
	while(('0'>c||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=0,c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
int cnt[N][3];
void solve(){
	int n=read(); ll k; scanf("%lld",&k);
	vector <int> vals;
	for(int i=1; i<=n; i++){
		int c=read(),w=read(),f=read();
		cnt[f][w]+=c;
		vals.push_back(f);
	}
	sort(all(vals),greater <int> ());
	vals.resize(unique(all(vals))-vals.begin());
	int f=0;
	for(int v:vals){
		if(cnt[v][1]>0&&f) cnt[v][1]--,f=0;
		cnt[v][2]+=(cnt[v][1]+1)/2;
		if(!f) f=cnt[v][1]%2?v:0;
	}
	k/=2;
	ll res=0,ans=0;
	for(int v:vals){
		int nt=cnt[v][2];
		cnt[v][1]=cnt[v][2]=0;
		if(nt<res) res-=nt;
		else{
			nt-=res;
			ans+=nt/k*v;
			nt%=k;
			if(nt) ans+=v,res=k-nt;
			else res=0;
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T=read();
	while(T--) solve();
	return 0;
}