#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=3e5+5;
int n;
ll K;
inline int red(){
	int data=0;bool w=0;char ch=getchar();
	while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
	if(ch=='-') w=1,ch=getchar();
	while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
	return w?-data:data;
}
int c[N],w[N],f[N];
struct lou{
	ll c1,c2;
	lou(){}
	lou(ll a,ll b):c1(a),c2(b){}
	void clear(){
		c1=c2=0;
	}
	void add(int tp,ll v){
		if(tp==1){
			c1+=v;
		}else{
			c2+=v;
		}
	}
	ll sum(){
		return c1+c2;
	}
	void show(){
		printf("C1: %lld C2: %lld\n",c1,c2);
	}
}flr[N];
ll ans;
map <int,int> lsh;
int ff[N],reff[N];
void solve(){
	int tot=0;
	lsh.clear();
	scanf("%d%lld",&n,&K);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&c[i],&w[i],&f[i]);
		ff[i]=f[i];
	}
	sort(ff+1,ff+n+1);
	for(int i=1;i<=n;i++){
		if(!lsh.count(ff[i])){
			lsh[ff[i]]=++tot;
			flr[tot].clear();
			reff[tot]=ff[i];
		}
	}
	for(int i=1;i<=n;i++){
		flr[lsh[f[i]]].add(w[i],c[i]);
	}
	//	for(int i=tot;i>=1;i--){
	//		if(flr[i].sum()<=0) continue;
	//		printf("%d: ",i);flr[i].show();
	//	}
	ans=0;
	int top1=tot,top2=tot,top=tot;
	while(top>0){
		while(top>0&&flr[top].sum()==0) top--;
		if(top==0) break;
		if(flr[top].c2*2>=K){
			ll need=flr[top].c2*2/K;
			ans+=reff[top]*need;
			//			printf("TOP2: %d: %lld\n",top,ans);
			flr[top].c2-=need*K/2;
		}
		if(flr[top].c1>=K){
			ll need=flr[top].c1/K;
			ans+=reff[top]*need;
			//			printf("TOP1: %d: %lld\n",top,ans);
			flr[top].c1-=need*K;
		}
		ll res=K-flr[top].c2*2;
		flr[top].c2=0;
		if(res>=flr[top].c1){
			res-=flr[top].c1;
			flr[top].c1=0;
		}else{
			flr[top].c1-=res;
			res=0;
		}
		//		printf("RES %d: %lld\n",top,res);
		if(res!=K){
			while(res>0&&(top1>0||top2>0)){
				while(top1>0&&flr[top1].c1==0) top1--;
				while(top2>0&&flr[top2].c2==0) top2--;
				if(top1==0&&top2==0) break;
				if(res==1&&top1==0) break;
				//				printf("%d %d: %lld\n",top1,top2,res);
				if(top2>top1&&res>1){
					if(res>=flr[top2].c2*2){
						res-=flr[top2].c2*2;
						flr[top2].c2=0;
						--top2;
					}else{
						ll need=res/2;
						flr[top2].c2-=need;
						res-=need*2;
					}				
				}else{
					if(res>=flr[top1].c1){
						res-=flr[top1].c1;
						flr[top1].c1=0;
						--top1;
					}else{
						flr[top1].c1-=res;
						res=0;
					}
				}
			}
			//			printf("TOP3: %d: %lld\n",top,ans+reff[top]);
			ans+=reff[top];
		}
		//		for(int i=maxf;i>minf;i--){
		//			printf("%d: ",i);flr[i].show();
		//		}
	}
	printf("%lld\n",ans);
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0); 
	int T=1;
	T=red();
	while(T--)solve();
	return 0;
}
/*
  2
  4 6
  1 1 8
  7 2 5
  1 1 7
  3 2 6
  8 1200000
  100000 1 100000
  100000 1 12345
  100000 2 100000
  100000 2 12345
  100000 1 100000
  100000 1 12345
  100000 2 100000
  100000 2 12345
  
 */