#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

#define int long long

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 1e5 + 5;

int n, k, ans;
vc<tuple<int, int, int> > a;

inline void testcase() {
	n = read(); k = read(); ans = 0; a.clear();
	for(int i = 1, u, v, w; i <= n; i++) 
		u = read(), v = read(), w = read(), a.pb(make_tuple(w, u, v));
	
	sort(a.begin(), a.end()); reverse(a.begin(), a.end());
	int res = 0, cnt = 0;
	for(auto &[f, c, w] : a) {
		if(w == 1) {
			int v = min(c, cnt);
			c -= v; cnt -= v;
		}
		if(c * w <= res) res -= c * w;
		else {
			if(res % 2 == 1 && w == 2) ++cnt;
			c -= res / w;
			ans += ((c * w - 1) / k + 1) * f;
			res = (c * w) % k;
			res = res ? k - res : 0;
		}
	}
	
	printf("%lld\n", ans);
}

signed main() {
	int t = read(); while(t--) testcase(); 
	return 0;
}