#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
	int x=0;
	char ch=getchar();bool f=0;
	while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
struct node{
	int num,w,flr,id;
};
vector<node> c1,c2;
bool cmp(node a,node b){
	return a.flr==b.flr?a.id>b.id:a.flr>b.flr;
}
int mis[100005];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=Read();
	for(int i=1;i<=T;i++){
		int n=Read(),k=Read();
		int ans=0;
		while(n--){
			mis[n]=0;
			int a=Read(),b=Read(),c=Read();
			if(b==1) c1.push_back({a,b,c,n});
			c2.push_back({a,b,c,n}); 
		}
		sort(c1.begin(),c1.end(),cmp);
		sort(c2.begin(),c2.end(),cmp);
//		for(int i=0;i<c2.size();i++){
//			cout<<c2[i].num<<' '<<c2[i].w<< ' '<<c2[i].flr<<' '<<c2[i].id<<endl;
//		}
		int p1=0;
		int rst=0;
		for(int i=0;i<c2.size();i++){
			if(c2[i].w==2){
				if(rst>=c2[i].num*2){
					rst-=c2[i].num*2;
					continue;
				}else{
					c2[i].num-=rst/2;
					rst%=2;
					if(rst==1){
						if(p1<c1.size()){
							c1[p1].num--;
//							cout << c1[p1].flr<<endl;
							rst=1;
							mis[c1[p1].id]++;
							rst=0;
						}
					}
				}
				ans+=c2[i].flr*(c2[i].num*2/k);
				c2[i].num%=k/2;
				if(c2[i].num){
					ans+=c2[i].flr;
					rst=k-c2[i].num*2;
				}
			}else{
				c2[i].num-=mis[c2[i].id];
//				cout <<c1[p1].id << ' '<<c2[i].id<<endl; 
				if(c1[p1].id==c2[i].id) p1++;
				if(rst>=c2[i].num) {rst-=c2[i].num;continue;}
				else c2[i].num-=rst,rst=0;
				ans+=c2[i].flr*(c2[i].num/k);
				c2[i].num%=k;
				if(c2[i].num){
					ans+=c2[i].flr;
					rst=k-c2[i].num;
				}
			}
//			cout << i << ' ' << ans << ' ' << rst <<endl;
		}
		c1.clear();c2.clear();
		printf("%lld\n",ans);
	}
	return 0;
}