#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+5;
int f[N][2];
void init(){
	for(int i=0;i<N;i++){
		f[i][0]=f[i][1]=0;
	}
}
void solve(){
	int n,k;cin>>n>>k;
	set<int>st1,st2;
	for(int i=0;i<n;i++){
		int c,w,f0;cin>>c>>w>>f0;
		f[f0][w-1]+=c;
		if(w==1) st1.insert(f0);
		else st2.insert(f0);
	}
	int ans=0;
	stack<int>St1,St2;
	for(auto x:st1){
		St1.push(x);
	}
	for(auto x:st2){
		St2.push(x);
	}
	while(!St1.empty()||!St2.empty()){
		if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())){
			int num1=St1.top();
			St1.pop();
			int cnt1=f[num1][0];
			int c=cnt1/k;
			if(cnt1%k!=0) c++;
			int res=c*k-cnt1;
			ans+=c*num1;
			f[num1][0]=0;
			while(res>0){
				if((res==1&&St1.empty())||(St1.empty()&&St2.empty())||res==1) break;
				if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())){
					int num1=St1.top();
					if(res>=f[num1][0]){
						res-=f[num1][0];
						f[num1][0]=0;
						St1.pop();
					}else{
						f[num1][0]-=res;
						res=0;
					}
				}else{
					int d=res/2;
					int num2=St2.top();
					if(d>=f[num2][1]){
						res-=f[num2][1]*2;
						f[num2][1]=0;
						St2.pop();
					}else{
						f[num2][1]-=d;
						res%=2;
					}
				}
				
			}
		}else{
			int num2=St2.top();
			St2.pop();
			int cnt2=f[num2][1];
			int k0=k/2;
			int c=cnt2/k0;
			if(cnt2%k0!=0) c++;
			int res=c*k-cnt2*2;
			ans+=c*num2;
			f[num2][1]=0;
			while(res>0){
				if((res==1&&St1.empty())||(St1.empty()&&St2.empty())) break;
				if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())||res==1){
					int num1=St1.top();
					if(res>=f[num1][0]){
						res-=f[num1][0];
						f[num1][0]=0;
						St1.pop();
					}else{
						f[num1][0]-=res;
						res=0;
					}
				}else{
					int d=res/2;
					int num2=St2.top();
					if(d>=f[num2][1]){
						res-=f[num2][1]*2;
						f[num2][1]=0;
						St2.pop();
					}else{
						f[num2][1]-=d;
						res%=2;
					}
				}
				
			}
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	init();
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}