// #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10, M = 1e4 + 10, MAXN = 1e5 + 10;
#define endl '\n'
#define int long long

struct node
{
	int c, w, f;
} q1[MAXN], q2[MAXN], a[MAXN];

bool cmp(node A, node B)
{
	return A.f < B.f;
}

int t1, t2;
int n, k;

signed main()
{
	int T;
	cin >> T;
	while(T --)
	{
		int ans(0);
		t1 = t2 = 0;
		cin >> n >> k;
		for(int i = 1; i <= n; ++ i)
		{
			cin >> a[i].c >> a[i].w >> a[i].f;
		}
		sort(a + 1, a + 1 + n, cmp);
		for(int i = 1; i <= n; ++ i)
		{
			if(a[i].w == 1)
			{
				q1[++ t1] = a[i];
			}
			else if(a[i].w == 2)
			{
				q2[++ t2] = a[i];
			}
		}
		while(t1 || t2)
		{
			int ava = k;
			if(q1[t1].f > q2[t2].f)
			{
				ans += q1[t1].f * (q1[t1].c / k);
				q1[t1].c %= k;
				if(q1[t1].c)
				{
					ans += q1[t1].f;
					ava -= q1[t1].c;
					t1 --;
					while(ava > 1 && (t1 || t2))
					{
						if(q1[t1].f > q2[t2].f)
						{
							int us = min(q1[t1].c, ava);
							ava -= us;
							q1[t1].c -= us;
							if(!q1[t1].c) -- t1;
						}
						else 
						{
							int us = min(q2[t2].c * 2, ava / 2 * 2);
							ava -= us;
							q2[t2].c -= us / 2;
							if(!q2[t2].c) -- t2;
							
						}
					}
					if(ava == 1 && (t1 || t2))
					{
						ava -= 1;
						q1[t1].c -= 1;
						if(!q1[t1].c) -- t1;
					}
				}
				else t1 --;
			}
			else
			{
				ans += q2[t2].f * (q2[t2].c * 2 / k);
				q2[t2].c %= (k / 2);
				if(q2[t2].c)
				{
					ans += q2[t2].f;
					ava -= q2[t2].c * 2;
					t2 --;
					while(ava > 1 && (t1 || t2))
					{
						if(q1[t1].f > q2[t2].f)
						{
							int us = min(q1[t1].c, ava);
							ava -= us;
							q1[t1].c -= us;
							if(!q1[t1].c) -- t1;
						}
						else 
						{
							int us = min(q2[t2].c * 2, ava / 2 * 2);
							ava -= us;
							q2[t2].c -= us / 2;
							if(!q2[t2].c) -- t2;
							
						}
					}
					if(ava == 1 && (t1 || t2))
					{
						ava -= 1;
						q1[t1].c -= 1;
						if(!q1[t1].c) -- t1;
					}
				}
				else t2 --;
			}
		}
		cout << ans << endl;
	}
	return 0;
}