#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
int T;
struct node{
	long long h,num,w;
};
node c[MAX];
int n,p;
long long k;
void findodd(){
	while(p<=n&&!(c[p].w==1&&c[p].num))
		p++;
}
// 快读 
long long read(){
	long long 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;
}
bool cmp(node x,node y){
	return x.h>y.h;
}
void solve(){
	n=read(),k=read();
	for(int i=1;i<=n;++i){
		c[i].num=read(),c[i].w=read(),c[i].h=read();
	}
	sort(c+1,c+1+n,cmp);
	cout<<"***"<<endl;
	for(int i=1;i<=n;++i)
		cout<<c[i].num<<" "<<c[i].w<<" "<<c[i].h<<endl;
	int cur=0;
	p=1;
	long long ans=0;
	while(cur<n){
		if(c[cur+1].num==0){
			cur++;
			continue;
		}
		
		long long sum=0;
		if(c[cur+1].num*c[cur+1].w<=k){
			ans+=c[cur+1].h;
			long long sum=0;
			while(cur<n&&sum+c[cur+1].num*c[cur+1].w<=k){
				sum+=c[cur+1].num*c[cur+1].w;
				c[cur+1].num=0;
				cur++;
			}
		//	cout<<cur<<endl;
			long long t=k-sum;
			if(cur<n){
				long long cnt=t/c[cur+1].w;
				c[cur+1].num-=cnt;
				sum+=c[cur+1].w*cnt;
				if(sum<k){
					
					findodd();
					if(p!=n+1){
						c[p].num--;
					}
				}
			}
		}
		else{
			long long t=c[cur+1].num*c[cur+1].w/k;
			ans+=c[cur+1].h*t;
			c[cur+1].num-=t*k/c[cur+1].w;
		}		
	}
	
	cout<<ans<<endl;
}
int main(){
	cin>>T;
	while(T--){
		solve();
	}
}