#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=1e5+5;
struct node{
	int c,f;
}a1[maxn],a2[maxn];
int cnt1,cnt2;
bool cmp(node a,node b){
	return a.f<b.f;
}
signed main()
{
    //ios::sync_with_stdio(false);
//    freopen("1.in","r",stdin);
	int T=read();
	while(T--){
		cnt1=0,cnt2=0;
		int n=read(),k=read();
		for(int i=1;i<=n;i++){
			int c=read(),w=read(),f=read();
			if(w==1){
				cnt1++;
				a1[cnt1].c=c;
				a1[cnt1].f=f;
			}else{
				cnt2++;
				a2[cnt2].c=c;
				a2[cnt2].f=f;
			}
		}
		sort(a1+1,a1+cnt1+1,cmp);
		sort(a2+1,a2+cnt2+1,cmp);
		
//		for(int i=cnt1;i>=1;i--) cout<<a1[i].c<<' '<<a1[i].f<<endl;
//		cout<<endl;
//		for(int i=cnt2;i>=1;i--) cout<<a2[i].c<<' '<<a2[i].f<<endl;
//		cout<<endl;
		stack<pii> q1,q2;
		for(int i=1;i<=cnt1;i++){
			q1.push(mp(a1[i].c,a1[i].f));
		}
		for(int i=1;i<=cnt2;i++){
			q2.push(mp(a2[i].c,a2[i].f));
		}
		int now_w=0,maxf=0,ans=000;
		while(!q1.empty()&&!q2.empty()){
//			cout<<000<<' '<<ans<<" "<<now_w<<' '<<maxf<<endl;
			if(q1.top().se>q2.top().se){
				int c=q1.top().fi,f=q1.top().se;q1.pop();
				if(!maxf) maxf=f;
				if(c+now_w>=k){
					ans+=maxf; 
					maxf=0;
					c-=k-now_w;
					now_w=0;
					ans+=f*(c/k);
					c%=k;
					if(c) q1.push(mp(c,f));
				}else{
					now_w+=c;
				}
			}else{
				int c=q2.top().fi,f=q2.top().se;q2.pop();
				if(!maxf) maxf=f;
				if(c*2+now_w>=k){
					ans+=maxf;
					c-=(k-now_w)/2;
					if((k-now_w)&1){
						q1.top().fi--;
						if(q1.top().fi==0) q1.pop();
						now_w=0;
						maxf=0;
					}else{
						now_w=0;
						maxf=0;
					}
					if(k&1){
						int tt=(c/(k/2));
						while(tt&&!q1.empty()){
							if(q1.top().fi>=tt){
								tt-=q1.top().fi;
								q1.pop();
							}else{
								q1.top().fi-=tt;
							}
						}
						ans+=f*(c/(k/2));
						c%=(k/2);
						if(c) q2.push(mp(c,f));
					}else{
						ans+=f*(c/(k/2));
						c%=(k/2);
						if(c) q2.push(mp(c,f));
					}
				}else{
					now_w+=c*2;
				}
			}
		}
		while(!q1.empty()){
//			cout<<111<<' '<<ans<<" "<<now_w<<' '<<maxf<<endl;
			int c=q1.top().fi,f=q1.top().se;q1.pop();
			if(!maxf) maxf=f;
			if(c+now_w>=k){
				ans+=maxf; 
				maxf=0;
				c-=k-now_w;
				now_w=0;
				ans+=f*(c/k);
				c%=k;
				if(c) q1.push(mp(c,f));
			}else{
				now_w+=c;
			}
		}
		while(!q2.empty()){
//			cout<<222<<' '<<ans<<" "<<now_w<<' '<<maxf<<endl;
			int c=q2.top().fi,f=q2.top().se;q2.pop();
			if(!maxf) maxf=f;
			if(c*2+now_w>=k){
				ans+=maxf; 
				maxf=0;
				c-=(k-now_w)/2;
				now_w=0;
				ans+=f*(c/(k/2));
				c%=(k/2);
				if(c) q2.push(mp(c,f));
			}else{
				now_w+=c*2;
			}
		}
		if(now_w) ans+=maxf;
		printf("%lld\n",ans);
	}
	
    return 0;
}