#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pr;
int const N=1e5+10;
ll n , k;
vector<pr >vc[2];
inline void solve()
{
	cin >> n >> k;
	vc[0].clear() , vc[1].clear();
	for(int i = 1 ; i <= n ; i++)
	{
		ll c , w , f; cin >> c >> w >> f;
		vc[__lg(w)].push_back({f , c});
	}
	sort(vc[0].begin() , vc[0].end() , greater<pr>());
	ll dt = 0;
	for(auto [f , c] : vc[0])
	{
		c -= dt , dt = c & 1;
		if(!c)continue ;
		vc[1].push_back({f , (c + 1) / 2});
	}
	sort(vc[1].begin() , vc[1].end() , greater<pr>());
	ll ans = 0; 
	k >>= 1 , dt = k;
	for(auto [f , c] : vc[1])
	{
		if(dt + c <= k)
			dt += c;
		else
		{
			dt += c;
			ll t = dt / k;
			dt -= t * k;
			ans += f * t;
		}
	}
	cout << ans << "\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while (t--) solve();
	return 0;
}