#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n,k,T;
inline int read() {
	int al = 0, fh = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			fh = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		al = al * 10 + ch - '0';
		ch = getchar();
	}
	return al * fh;
}
struct node {
	int c, w, f;
} a[N];
bool cmp(node a, node b) {
	return a.f > b.f;
}
signed main() {
	T = read();
	for (int yyc = 1; yyc <= T; yyc++) {
		n = read();
		k = read();
		for (int i = 1; i <= n; i++) {
			a[i].c = read();
			a[i].w = read();
			if (a[i].w == 2)
				a[i].c *= 2;
			a[i].f = read();
		}
		sort(a + 1, a + n + 1, cmp);
		int ans = 0, now = 0;
		for (int i = 1; i <= n; i++) {
			if (now != 0) {
				if (now + a[i].c <= k) {
					now = now + a[i].c;
					now %= k;
					continue;
				}
				else {
					a[i].c -= k - now;
					now = 0;
				}
			}
			ans += a[i].f * (a[i].c / k);
			a[i].c %= k;
			now = a[i].c;
			if (now != 0)
				ans += a[i].f;
		}
		cout << ans << endl;
	}
}