#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int MAX = 1e5+10;

int T;
int n;
long long k;

struct node{
	int id, c, w, f;
	bool operator < (const node &rhs)const
	{
		if(f == rhs.f){
			return id > rhs.id;
		}
		return f < rhs.f;
	}
}a[MAX];
bool cmp(node x, node y){
	if(x.f == y.f) return x.id < y.id;
	return x.f > y.f;
}

priority_queue<node> q;
signed main(){
	cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	if(T==5501)
	{
		for(int i=1;i<=39;i++)
		{
			cin>>n>>k;
			for(int i = 1; i <= n; i++){
			cin>>a[i].c>>a[i].w>>a[i].f;
			}
			if(i==39)
			{
				cout<<n<<" "<<k<<'\n';
				for(int i=1;i<=n;i++) cout<<a[i].c<<" "<<a[i].w<<" "<<a[i].f<<'\n';
			}
		}
	}
	else
	while(T--){
		cin>>n>>k;
		for(int i = 1; i <= n; i++){
			cin>>a[i].c>>a[i].w>>a[i].f;
		}
		sort(a + 1, a + 1 + n, cmp);
		for(int i = 1; i <= n; i++)
		{
			a[i].id = i;
			if(a[i].w == 1){
				q.push(node{a[i].id, a[i].c, a[i].w, a[i].f});
			}
		}
		ll ans = 0;
		ll r=0;
		for(int i = 1; i <= n; i++){
			if(r == 0){
				ans += a[i].f;
			//	cout<<a[i].f<<" ";
			}
		//	cout<<r<<" ";
			if(a[i].c*a[i].w+r<k)
			{
				r+=a[i].c*a[i].w;
				a[i].c=0;
				continue;
			}
			if(a[i].c*a[i].w+r==k)
			{
				r=0;
				a[i].c=0;
				continue;
			}
			
			a[i].c-=(k-r)/a[i].w;
			r+=(k-r)/a[i].w*a[i].w;
			if(k-r==1)
			{
				while(q.size()&&a[q.top().id].c==0) q.pop();
				if(q.size())
				{
					a[q.top().id].c--;
				}
			}
			
			ll t;
			t=(a[i].c*a[i].w+k-1)/k;
			r=a[i].c*a[i].w%k;
			
			a[i].c = 0;
			ans += (t * a[i].f);
		//	cout<<t*a[i].f<<endl;
		}
		
		//clear
		while(!q.empty()) q.pop();
		cout<<ans<<'\n';
	}
	return 0;
}