#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const int mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
void init(){ }
ll n,k,now;
struct Node{
	ll c, w, f;
}s[100005];

void doit(){
	while(now<=n){
		if(!s[now].c || s[now].w!=1) now ++;
		else break;
	}
	if(now<=n) s[now].c --;
}
void procedure(){
	n=read(), k=read();
	for(ll i=1;i<=n;i++){
		s[i].c=read(), s[i].w=read(), s[i].f=read();
	}
	sort(s+1, s+n+1, [](Node A, Node B){ return A.f > B.f; });
	ll pt=1, ans=0; now=1;

	// for(ll i=1;i<=n;i++){
	// 	for(ll j=1;j<=s[i].c;j++)
	// 		cout<<s[i].w<<" "<<s[i].f<<endl;
	// }
	while(pt<=n){
		while(1){
			while(pt <= n && s[pt].c == 0) pt ++;
			if(pt > n) break;
			ans += s[pt].c*s[pt].w/k*s[pt].f;
			s[pt].c %= (k/s[pt].w);
			if(!s[pt].c) pt++;
			else break;
			if(pt > n) break;
		}
		if(pt > n) break;


		ans += s[pt].f;
		// cout<<"here max = "<<s[pt].f<<endl;

		ll res=k-s[pt].w*s[pt].c, cur=pt+1;

		s[pt].c = 0;
		while(cur<=n && res){
			// cout<<"cur = "<<cur<<endl;
			// usleep(100000);
			if(s[cur].w * s[cur].c <= res){
				res -= s[cur].w * s[cur].c;
				s[cur].c = 0;
				cur ++;
			}else{
				ll q = res / s[cur].w;
				s[cur].c -= q;
				res -= q * s[cur].w;
				break;
			}
		}
		if(res) doit();
		pt = cur;
	}
	printf("%lld\n", ans);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=read();
	init();
	while(T--) procedure();
	return 0;
}