#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
const int N=1e5+5;
struct node{
	int c,w,f;
}re[N];
inline bool cmp(node x,node y)
{
	if(x.f!=y.f) return x.f>y.f;
	return x.w>y.w;
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++) cin>>re[i].c>>re[i].w>>re[i].f;
		int ans=0;
		int res=0;
		int cnt=0;
		sort(re+1,re+n+1,cmp);
		for(int i=1;i<=n;i++)
		{
			if(re[i].w==1) 
			{
				int t=min(cnt,re[i].c);
				re[i].c-=t;
				cnt-=t;
			}
			if(res>=re[i].c*re[i].w)
			{
				res-=re[i].c*re[i].w;
				if(res==1) res=0, cnt++;
				continue;
			}
			int t=res/re[i].w;
			re[i].c-=t;
			res-=re[i].w*t;
			if(res==1) res=0, cnt++;
			int p=(re[i].c*re[i].w+k-1)/k;
			ans+=p*re[i].f;
			res=k*p-(re[i].c*re[i].w);
			if(res==1) res=0, cnt++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}