#include <bits/stdc++.h>
using namespace std;
struct t1
{
	long long c,w,f;
}t[100005];
bool cmp(t1 a,t1 b)
{
	if(a.f!=b.f)
	{
		return a.f>b.f;
	}
	return a.w>b.w;
}
long long ans,k;
long long cur,n;
void solve(int i,long long l,bool f)
{
	if(l%2==1&&f)
	{
		cout<<"!!!"<<endl;
		exit(0);
	}
	if(i==n+1)
	{
		return;//边界，1~n都已处理完成 
	}
	if(l==1)
	{
		ans=ans+cur;
		cur=0;
		solve(i,k,f=true);
		return;//保证以下的l至少为2 
	}
	if(t[i].w==1&&f)
	{
		t[i].c--;
		f=false;
		if(!t[i].c)
		{
			solve(i+1,l,f);
			return;
		}
	}//处理f标记，若f标记未去除，则w必定为2 
	if(l/t[i].w>t[i].c)
	{
		cur=max(cur,t[i].f);
		solve(i+1,l-t[i].c*t[i].w,f);
	}//容量绰绰有余 
	else if(l/t[i].w==t[i].c)
	{
		cur=max(cur,t[i].f);
		ans=ans+cur;
		cur=0;
		solve(i+1,k,l%t[i].w);
	}//容量刚好够 
	else
	{
		cur=max(cur,t[i].f);//至少能运载一个 
		ans=ans+cur;
		cur=0;
		t[i].c-=(l/t[i].w);
		ans=ans+t[i].c/(k/t[i].w)*t[i].f;
		t[i].c%=(k/t[i].w);
		if(t[i].c)
		{
			solve(i,k,l%t[i].w);
		}
		else
		{
			solve(i+1,k,l%t[i].w);
		}
	}//容量不够 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
//	freopen("L.in","r",stdin);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>t[i].c>>t[i].w>>t[i].f;
		}
		sort(t+1,t+n+1,cmp);
		cur=ans=0;
		solve(1,k,false);//只有w=1才有可能产生标记，而每次w=1都会删除原来的标记 
		cout<<ans+cur<<"\n";
	}
	return 0;
}