#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;

ll n,k,lf1[N];
struct node{
	ll c,w,f;
}a[N];

bool bol(node a,node b){
	return a.f<b.f;
}



int main(){
	int T; cin>>T;
	while(T--){
		cin>>n>>k;
		for(int i=0;i<n;i++){
			cin>>a[i].c>>a[i].w>>a[i].f;
		}
		sort(a,a+n,bol);
//		for(int i=0;i<n;i++) cout<<a[i].c<<"\t";
//		cout<<endl;
//		for(int i=0;i<n;i++) cout<<a[i].w<<"\t";
//		cout<<endl;
//		for(int i=0;i<n;i++) cout<<a[i].f<<"\t";
//		cout<<endl;
		
		ll pre=-1;
		for(int i=0;i<n;i++){
			lf1[i]=pre;
			if(a[i].w==1) pre=i;
		}
//		for(int i=0;i<n;i++) cout<<lf1[i]<<"\t";
//		cout<<endl;
		ll ans=0;
		ll prek=k,pref=a[n-1].f;
		for(int i=n-1;i>=0;i--){
			ll C=a[i].c,W=a[i].w,F=a[i].f;
			if(a[i].c*a[i].w<prek){
				prek-=a[i].c*a[i].w;
				if(prek%2==1){
					int tmp=i;
					while(a[lf1[tmp]].c==0&&lf1[tmp]!=-1){
						tmp=lf1[tmp];
					}
					if(lf1[tmp]!=-1) a[lf1[tmp]].c--;
					a[i].c++;
				}
				continue;
			}
			else if(prek!=0||prek!=k){
				ans+=pref;
				a[i].c-=prek/a[i].w;
			}
			ans+=a[i].f*(a[i].c*a[i].w/k);
			ll cc=a[i].c;
//			cout<<
			a[i].c=(a[i].c*a[i].w%k)/a[i].w;
			cc=a[i].c;
			if(a[i].c*a[i].w%2==1){
				int tmp=i;
				while(a[lf1[tmp]].c==0&&lf1[tmp]!=-1){
					tmp=lf1[tmp];
				}
				if(lf1[tmp]!=-1) a[lf1[tmp]].c--;
				a[i].c++;
			}
			if(i==0&&a[i].c!=0) ans+=a[i].f;
			prek=k-a[i].c*a[i].w;
			pref=a[i].f;
			
//			cout<<ans<<"\t";
//			if(prek==0){
//				prek=k;
//				continue;
//			}
		}
//		cout<<endl;
		cout<<ans<<endl;
	}
	return 0;

}