#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	int T; cin >> T;
	for(int t = 0; t < T; t++) {
		ll N, K; cin >> N >> K;
		vector<pair<ll,ll>> W1, W2;
		for(int i = 0; i < N; i++) {
			int C,W,F; cin >> C >> W >> F;
			if(W == 1) W1.push_back({F,C});
			else W2.push_back({F,C});
		}

		sort(W1.begin(), W1.end());

		for(int j = W1.size()-1; j >= 0; j--) {
			ll cj = (W1[j].second + 1)/2;
			if(cj > 0) W2.push_back({W1[j].first, cj});
			if(W1[j].second % 2) {
				if(j-1 > 0) W1[j-1].second--;
			}
		}

		sort(W2.begin(), W2.end());

		ll R = 0;
		K /= 2;
		while(W2.size()) {
			R += (W2.back().second/K)*W2.back().first;
			W2.back().second %= K;
			if(W2.back().second) {
				R += W2.back().first;
				ll g = K;
				while(g>0) {
					ll m = min(g, W2.back().second);
					g -= m;
					W2.back().second -= m;
					if(!W2.back().second) W2.pop_back();
				}
			} else W2.pop_back();
		}


		cout << R << endl;

	}
}