#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long

const int N=100010;
int n,K;
struct Node{
	int num,w,f;
	inline bool operator<(const Node that){
		return f<that.f;
	}
}a[N];

signed main()
{
	int T;
	scanf("%lld",&T);
	for(int _=1;_<=T;_++)
	{
		scanf("%lld%lld",&n,&K);
		for(int i=1;i<=n;i++)
			scanf("%lld%lld%lld",&a[i].num,&a[i].w,&a[i].f);
		//if(_==39)
		//{
		//	for(int i=1;i<=17;i++)
		//		cout<<" "<<a[i].num<<" "<<a[i].w<<" "<<a[i].f<<" ";
		//}
		sort(a+1,a+1+n);
		//cout<<endl;
		//for(int i=1;i<=n;i++)
		//	cout<<i<<" : "<<a[i].num<<" "<<a[i].w<<" "<<a[i].f<<endl;

		int fir=-1,pos=0,j=n,ans=0;
		for(int i=n,j=n;i;j--)
		{
			if(!a[i].num)
			{
				i--;
				continue;
			}
			if(a[i].num*a[i].w+pos<K)
			{
				if(fir==-1)fir=a[i].f;
				pos+=a[i].num*a[i].w;
				i--;
			}
			else
			{
				if(((K-pos)&1) && a[i].w==2)
				{
					while((a[j].w!=1||j>=i||!a[j].num) && j)j--;
					a[j].num--;
					pos++;
				}
				
				a[i].num-=(K-pos)/a[i].w;
				if(fir==-1)fir=a[i].f;
				ans+=fir;
				fir=-1;
				pos=0;
				
				int t=a[i].num*a[i].w/K;
				ans+=t*a[i].f;
				a[i].num-=t*K/a[i].w;
				if(!a[i].num)i--;
			}
			//cout<<"i "<<j<<" "<<ans<<" "<<pos<<" "<<fir<<" "<<endl;
		}
		if(fir!=-1)ans+=fir;
		printf("%lld\n",ans);
	}
	return 0;
}