#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int t,n;
ll k;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>k;
		map<int,ll> c1,c2;
		vi poss;
		for (int i=0;i<n;++i)
		{
			int c,w,f;
			cin>>c>>w>>f;
			poss.pb(f);
			if (w==1) c1[f]+=c;
			else c2[f]+=c;
		}
		sort(all(poss));
		poss.erase(unique(all(poss)),poss.end());
		reverse(all(poss));
		ll an=0,rem=0;
		for (auto x: poss)
		{
			ll u2=min(c2[x],rem/2);
			c2[x]-=u2;
			rem-=2*u2;
			ll u1=min(c1[x],rem);
			c1[x]-=u1;
			rem-=u1;
			if (rem==0 || (rem==1 && c2[x]))
			{
				ll sw=2*c2[x]+c1[x];
				an+=(sw+k-1)/k*x;
				rem+=(k-sw%k)%k;
			}
		}
		cout<<an<<en;
	}
}