/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int del[100005];
void solve()
{
	int n,K,ans=0;
	cin>>n>>K;
	vector <array<int,4> > vec,vec1;

	for(int i=1;i<=n;i++)
	{
		del[i]=0;
		int c,w,f;
		cin>>c>>w>>f;
		vec.pb({f,w,c,i});
		if(w==1) vec1.pb({f,w,c,i});
	}
	sort(vec.begin(),vec.end());
	sort(vec1.begin(),vec1.end()); 
	while(vec.size())
	{
		if(vec.back()[1]==1)
		{
			vec.back()[2]-=del[vec.back()[3]];
			del[vec.back()[3]]=0;
			if(!vec.back()[2])
			{
				if(vec1.size()&&vec1.back()[3]==vec.back()[3]) vec1.pop_back();
				vec.pop_back();
				continue;
			}
		}
		int tr=vec.back()[2]/(K/vec.back()[1]);
		if(vec.back()[2]%(K/vec.back()[1])==0) tr--;
		ans+=vec.back()[0]*tr;
		vec.back()[2]-=tr*(K/vec.back()[1]);
		ans+=vec.back()[0];
//		cout<<vec.back()[0]<<" "<<vec.back()[1]<<" "<<vec.back()[2]<<" "<<tr<<"\n"; 
		int nw=K;
		while(nw&&vec.size())
		{
			if(nw==1)
			{
				if(vec1.size())
				{
					del[vec1.back()[3]]++;
					vec1.back()[2]--;
					if(!vec1.back()[2]) vec1.pop_back();
				}
				break;
			}
			else if(vec.back()[1]==2)
			{
				int d=min(nw/2,vec.back()[2]);
				nw-=2*d,vec.back()[2]-=d;
				if(!vec.back()[2]) vec.pop_back();
			}
			else
			{
				vec.back()[2]-=del[vec.back()[3]];
				del[vec.back()[3]]=0;
				int d=min(nw,vec.back()[2]);
				nw-=d,vec.back()[2]-=d;
				if(vec1.size()&&vec1.back()[3]==vec.back()[3]) vec1.back()[2]-=d;
				if(!vec.back()[2]) 
				{
					if(vec1.size()&&vec1.back()[3]==vec.back()[3]) vec1.pop_back();
					vec.pop_back();
				}
			}
		}
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}