#include <bits/stdc++.h>
using namespace std;

using ll = long long ;

void solve() {
	ll n, k;
	cin >> n >> k;
	
	vector<array<int, 2>> tmp, vec;
	 
	for (int i = 1; i <= n; i++) {
		int c, w, f;
		cin >> c >> w >> f;
		if (w == 1) tmp.push_back({f, c});
		else vec.push_back({f, c});
	}
	
	sort(tmp.begin(), tmp.end());
	
	for (int i = int(tmp.size()) - 1; i > 0; i--) if (tmp[i][1]) {
		if (tmp[i][1] & 1) {
			tmp[i][1]++;
			tmp[i - 1][1]--;
		}
		vec.push_back({tmp[i][0], tmp[i][1] / 2});
	}
	if (tmp[0][1]) vec.push_back({tmp[0][0], (tmp[0][1] + 1) / 2});
	
	k /= 2;
	
	sort(vec.begin(), vec.end());
	
	ll ans = 0;
	for (int i = int(vec.size()) - 1; i >= 0; i--) {
		
		int cnt = vec[i][1] / k;
		vec[i][1] %= k;
		
		ans += (ll)vec[i][0] * cnt;
		
		if (vec[i][1]) {
			int j = i;
			ll sum = vec[i][1];
		
			while (j > 0 && sum + vec[j - 1][1] <= k) {
				sum += vec[--j][1];
			}
			
			if (j > 0) vec[j - 1][1] -= k - sum;
			ans += vec[i][0];
			
			i = j;
		}
	}
	
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--)
	solve();
	return 0;
}