#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> PII;
void solve(){
	int n,k;
	cin>>n>>k;
	vector<array<int,3>>a(n);
	for(int i=0;i<n;i++){
		auto &[h,cnt,w]=a[i];
		cin>>cnt>>w>>h;
	}
	sort(a.begin(),a.end(),greater<>());
	int prew=0,preh=a[0][0],ans=0;
	for(int i=0;i<n;i++){
		auto [h,cnt,w]=a[i];
		if(w*cnt+prew>=k){//这次够，还有剩的
			if(preh==h){
				ans+=(w*cnt+prew)/k*preh;
//				cout<<preh<<" "<<h<<" "<<w*cnt+prew<<" "<<(w*cnt+prew)-k<<endl;
			}else{
//				cout<<preh<<" "<<h<<" "<<w*cnt+prew<<" "<<(w*cnt+prew)-k<<endl;
				ans+=preh;
				int t=(w*cnt+prew-k)/k;
				if(t>=1)ans+=t*h;
			}
			if((w*cnt+prew)%k!=0)preh=h;
			else preh=a[i+1][0];
			prew=(w*cnt+prew)%k;
		}else{//不够，还要等下一次
			preh=max(preh,h);
			prew+=cnt*w;
		}
	}
	if(prew>0){
		ans+=(prew+k-1)/k*preh;
	}
	cout<<ans<<endl;
}
signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)solve();
	return 0;
}