/*
¤ï¤ó¤ï¤ó¡­¡­¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
	LL x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(LL x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
typedef pair<LL,LL> P;
typedef vector<LL> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
struct node{
	LL c,w,h;
	node(LL C=0,LL W=0,LL H=0){c=C,w=W,h=H;}
	inline bool operator < (node f) const {return h<f.h || (h==f.h && w<f.w);}
}a[100005];
LL n,k;
LL cnt,id[100005];
void Solve()
{
	n=read(),k=read();
	for(LL i=1;i<=n;++i)
	{
		LL c=read(),w=read(),h=read();
		a[i]=node(c,w,h);
	}
	sort(a+1,a+1+n);
	cnt=0;
	for(LL i=1;i<=n;++i)	if(a[i].w==1)	id[++cnt]=i;
	LL p=n,ans=0;
	while(p>=1)
	{
		if(a[p].c==0)
		{
			--p;
			continue;
		}
		LL r=k;
		ans+=a[p].h;
		while(1)
		{
			LL c=a[p].c,w=a[p].w;
			if(c*w>r)
			{
				a[p].c-=r/w;
				r-=r/w*w;
				if(r)
				{
					while((id[cnt]>=p || a[id[cnt]].c==0) && cnt>=1)	--cnt;
					if(cnt>=1)	--a[id[cnt]].c;
				}
				break;
			}
			r-=c*w;
			--p;
			if(p==0)	break;
		}
	}
	write(ans),etr;
}
int main(){
	LL T=read();
	while(T-->0)	Solve();
	return 0;
}