#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int TC, N;
ll K;


int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	scanf("%d", &TC);
	while(TC--)
	{
		scanf("%d%lld", &N, &K);
		map<int, ll> M1, M2;
		for(int i=1; i<=N; i++)
		{
			int c, w, f;
			scanf("%d%d%d", &c, &w, &f);
			if(w==1) M1[f]+=c;
			else M2[f]+=c;
		}
		
		ll flag=0;
		while(!M1.empty())
		{
			auto it=prev(M1.end());
			if(flag) { it->second--; flag=0; }
			M2[it->first]+=(it->second+1)/2;
			if(it->second%2) flag=1;
			M1.erase(it);
		}

		K/=2;
		flag=0;
		ll ans=0;

		while(!M2.empty())
		{
			auto it=prev(M2.end());
			ll t=min(flag, it->second);
			it->second-=t; flag-=t;
			if(it->second==0)
			{
				M2.erase(it);
				continue;
			}
			t=(it->second+K-1)/K;
			ans+=t*it->first;
			it->second-=t*K;
			flag=-it->second;
			M2.erase(it);
		}
		printf("%lld\n", ans);
	}
}