#pragma GCC optimize(3, "Ofast", "inline")
#define FOR(i, a, b) for(int i = (a); i <= (b); i ++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i --)
#define debug(x) cerr << (#x) << ": " << (x) << '\n'
#define pb push_back
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef array<int, 2> pii;
typedef array<ll, 2> pll;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n, k;

void solve(int T) {
	cin >> n >> k;
	vector<array<int, 3>> a(n + 1, {0, 0, 0});
	FOR(i, 1, n) {
		cin >> a[i][2] >> a[i][1] >> a[i][0];
	}
	sort(a.begin() + 1, a.end());
	int now = 0, mx = 0, ans = 0;
	int t1 = n, t2 = n;
	while(t1 != 0 || t2 != 0) {
		while(t1 > 0 && (a[t1][1] != 1 || a[t1][2] == 0)) t1 --;
		while(t2 > 0 && (a[t2][1] != 2 || a[t2][2] == 0)) t2 --;
		// debug(t1), debug(t2), debug(now), debug(mx), debug(ans);
		if(t1 > t2) {
			if(a[t1][2] * a[t1][1] + now < k) {
				now += a[t1][2] * a[t1][1], mx = max(mx, a[t1][0]);
				t1 --;
				continue;
			}
			int t = k - now;
			if(now > 0) ans += mx;
			else ans += a[t1][0];
			a[t1][2] -= t, mx = now = 0;
			t = a[t1][2] / k;
			ans += t * a[t1][0];
			a[t1][2] -= t * k;
			if(a[t1][2]) now += a[t1][2] * a[t1][1], mx = max(mx, a[t1][0]);
			t1 --;
		}
		else {
			if(a[t2][2] * a[t2][1] + now < k) {
				now += a[t2][2] * a[t2][1], mx = max(mx, a[t2][0]);
				t2 --;
				continue;
			}
			int t = (k - now) / 2;
			if((k - now & 1) && t1 > 0) a[t1][2] --;
			if(now > 0) ans += mx;
			else ans += a[t2][0];
			a[t2][2] -= t, mx = now = 0;
			t = a[t2][2] / (k / 2);
			ans += t * a[t2][0];
			a[t2][2] -= t * (k / 2);
			if(a[t2][2]) now += a[t2][2] * a[t2][1], mx = max(mx, a[t2][0]);
			t2 --;
		}
	}
	if(now != 0) ans += mx;
	cout << ans << '\n';
}

void init() {

}

signed main() {
	IOS;
	int t = 1;
	cin >> t;
	init();
	FOR(T, 1, t) {
		solve(T);
	}
  	return 0;
}