#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool cmp(pair<ll,ll> a,pair<ll,ll> b){
	return a.first>=b.first;
}


void solve(){
	ll n,k;
	vector<pair<ll,ll> > a;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		ll x,y,z;
		cin>>x>>y>>z;
		a.push_back({z,x*y});
	}
	a.push_back({0,1});
	sort(a.begin(),a.end(),cmp);
	ll ans=0;
	ll now=a[0].first,sum=0;
	for(auto it:a){
		sum+=it.second;
	   if(sum>k){
	   	  ans+=now;
	   	  sum-=k;
	   	  now=it.first;
	   	  ll c=(sum-1)/k;
	   	  ans=ans+c*now;
	   	  sum=sum-c*k;
	   }
	}
	ans+=now;
	cout<<ans<<endl;
}


int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}