#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl

#define re
inline void Rd(int &res){
    re char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
inline void Rd(ll &res){
    re char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}

const int N = 200005;
int n;
ll k;
int n1, n2;
array<int, 2> A[N], B[N];

int main() {
	int T; Rd(T); while (T--) {
		Rd(n); Rd(k);
		n1 = n2 = 0;
		for (int i = 1, c, w, f; i <= n; ++i) {
			scanf("%d%d%d", &c, &w, &f);
			if (w == 2) {
				A[++n2] = {f, c};
			} else {
				B[++n1] = {f, c};
			}
		}
		sort(B + 1, B + n1 + 1);
		for (int i = n1; i >= 1; --i) {
			if (B[i][1] & 1) {
				A[++n2] = {B[i][0], (B[i][1] + 1) / 2};
				if (i > 1) B[i - 1][1] -= 1;
			} else {
				A[++n2] = {B[i][0], B[i][1] / 2};
			}
		}
		sort(A + 1, A + n2 + 1);
		reverse(A + 1, A + n2 + 1);
		k >>= 1;
		ll cur = 0;
		ll ans = 0;
		ll lst = 0;
		for (int i = 1; i <= n2; ++i) {
			ll num = A[i][1];
			ll val = A[i][0];
			// out(num); outln(val);
			if (cur) {
				if (num >= k - cur) {
					ans += lst;
					num -= k - cur;
					if (num % k != 0) lst = val;
					ans += num / k * val;
					cur = num % k;
				} else {
					cur += num;
				}
			} else {
				if (num % k != 0) lst = val;
				ans += num / k * val;
				cur = num % k;
			}
		}
		if (cur) ans += lst;
		printf("%lld\n", ans);
	}
	return 0;
}