#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
struct dat{
	int c,w,f;
	bool operator<(const dat&rhs)const{
		if(f!=rhs.f)return f>rhs.f;
		return w>rhs.w;
	};
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;
	for(;T--;)
	{
		int N;
		long long K;
		cin>>N>>K;
		vector<dat>cwf(N);
		for(int i=0;i<N;i++)
		{
			int c,w,f;cin>>c>>w>>f;
			cwf[i]=(dat){c,w,f};
		}
		sort(cwf.begin(),cwf.end());
		long long ans=0;
		bool rest1=false;
		long long k=0;
		for(dat t:cwf)
		{
			int c=t.c,w=t.w,f=t.f;
			if(w==1)
			{
				if(rest1)
				{
					c--;
					rest1=false;
				}
				if(k>=c)
				{
					k-=c;
					continue;
				}
				c-=k;
				ans+=(long long)f*(c/K);
				c%=K;
				if(c==0)k=0;
				else
				{
					ans+=f;
					k=K-c;
				}
			}
			else
			{
				if(k>=2*c)
				{
					k-=2*c;
					continue;
				}
				if(k%2==1)
				{
					assert(!rest1);
					rest1=true;
					k--;
				}
				assert(k%2==0);
				c-=k/2;
				ans+=(long long)f*(c/(K/2));
				c%=K/2;
				if(c==0)k=0;
				else
				{
					ans+=f;
					k=K-c*2;
				}
			}
		}
		cout<<ans<<"\n";
	}
}