#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
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 a, node b){
	if(a.f == b.f) return a.id < b.id;
	return a.f > b.f;
}

priority_queue<node> q;
int main(){
	cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	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(r==1)
			{
				while(q.size()&&a[q.top().id].c==0) q.pop();
				if(q.size())
				{
					a[q.top().id].c--;
				}
				r=0;
			}
			
			
			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;
}