#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
struct qxl
{
	int c,f;
}q[N],e[N];
bool cmp(qxl a,qxl s)
{
	return a.f>s.f;
}
int t,n,k,qn,en,c,w,f,l,r,a,s,d,z,ans,p,o,mf,pp;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>k;
		qn=0;en=0;
		for (int i=1;i<=n;i++)
		{
			cin>>c>>w>>f;
			if (w==1) 
			{
				qn++;
				q[qn].c=c;q[qn].f=f;
			} else
			{
				en++;
				e[en].c=c;e[en].f=f;
			}
		}
		sort(q+1,q+1+qn,cmp);
		sort(e+1,e+1+en,cmp);
		l=1;
		r=1;
		a=0;
		ans=0;
		p=0;o=100005;mf=0;pp=0;
		while(l<=qn||r<=en)
		{
			if (q[l].f<=e[r].f)
			{
				if (a!=0)
				{
					s=min(e[r].c,(k-a)/2);
					e[r].c-=s;
					a+=s*2;
					if (e[r].c==0)
					{
						r++;
						continue;
					}
					if (k-a==1)
					{
						if (q[l].c)
							{
								q[l].c--;
								if (!q[l].c)
									l++;
							}else 
					{
						if (p)o=min(o,p); else 
						{
							if (pp==0)pp=mf;	
						}
					}	
					} 
					a=0;
					mf=0;
				}
				p=0;
				d=k/2;
				z=e[r].c/d;
				ans+=z*e[r].f;
				e[r].c-=z*d;
				if (k%2)
				{
					while (l<qn&&z>0)
					{
						s=min(z,q[l].c);
						z-=s;
						q[l].c-=s;
						if (q[l].c==0) l++;
					}
					if (z>0)
					{
						if (pp==0)pp=e[r].f;
						a=k-1;
					}
				}
				if (e[r].c)
				{
					ans+=e[r].f;
					a=e[r].c*2;
					e[r].c=0;
					mf=e[r].f;
				}
				r++;	
			} else
			{
				if (a!=0)
				{
					s=min(q[l].c,(k-a));
					q[l].c-=s;
					p=q[l].f;
					a+=s;
					if (q[l].c==0)
					{
						l++;
						continue;
					}
					a=0;
				}
				d=k;
				z=q[l].c/d;
				ans+=z*q[l].f;
				q[l].c-=z*d;
				if (q[l].c)
				{
					p=q[l].f;
					ans+=q[l].f;
					a=q[l].c;
					q[l].c=0;
				}
				l++;	
			}
		}
		if (a==2)
		{
			if (e[r-1].f+pp-o>0) ans-=e[r-1].f+pp-o;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
/*
1
5 7
5 1 5
3 1 4
6 2 8
5 2 3
4 2 2
*/