#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
	int c,f;
}a1[100005],a2[100005];
bool cmp(node a,node b) {
	return a.f>b.f;
}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
void work() {
	int n,m,n1=0,n2=0;
	int c,w,f;
	read(n);
	read(m);
	for(int i=1;i<=n;i++) {
		read(c);
		read(w);
		read(f);
		if(w==1) {
			n1++;
			a1[n1].c=c;
			a1[n1].f=f;
		} else {
			n2++;
			a2[n2].c=c;
			a2[n2].f=f;
		}
	}
	sort(a1+1,a1+n1+1,cmp);
	sort(a2+1,a2+n2+1,cmp);
	int l1=1,l2=1,sum=0,ans=0;
	while(l1<=n1||l2<=n2) {
		if(l1<=n1&&a1[l1].f>a2[l2].f||l2>n2) {
			if(sum==0) ans+=a1[l1].f;
			if(sum+a1[l1].c<=m) {
				sum+=a1[l1].c;
				l1++;
			} else {
				a1[l1].c-=m-sum;
				sum=0;
			}
		} else if(l2<=n2) {
			if(sum==0) ans+=a2[l2].f;
			if(sum+2*a2[l2].c<=m) {
				sum+=2*a2[l2].c;
				l2++;
			} else {
				a2[l2].c-=(m-sum)/2;
				if((m-sum)%2==1) {
					if(l1<=n1) {
						a1[l1].c--;
						if(a1[l1].c==0) l1++;
					}
				}
				sum=0;
			}
		}
	}
	cout<<ans<<"\n";
}
signed main() {
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}