// In the name of Allah

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

typedef 	long long int			ll;
typedef 	long double				ld;
typedef 	pair<int, int>			pii;
typedef 	pair<ll, ll>			pll;
typedef 	complex<ld>				cld;

#define 	all(x)					(x).begin(),(x).end()
#define 	len(x)					((ll) (x).size())
#define 	F						first
#define 	S						second
#define		X						real()
#define		Y						imag()
#define 	pb						push_back
#define 	sep						' '
#define 	endl					'\n'
#define 	Mp						make_pair
#define 	kill(x)					cout << x << '\n', exit(0)
#define 	set_dec(x)				cout << fixed << setprecision(x);
#define 	file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

int n; ll k;
vector<pll> A1, A2;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		A1.clear(); A2.clear();
		
		cin >> n >> k;
		ll r = 0; k /= 2;
		for (int i = 0; i < n; i++) {
			ll c, w, f;
			cin >> c >> w >> f;
			if (w == 1) A1.pb(Mp(f, c));
			else A2.pb(Mp(f, c));
			if (w == 1) r += c;
		}
		
		sort(all(A1));
		if (r % 2 == 1) {
			A1[0].S--;
			A2.pb(Mp(A1[0].F, 1));
		}
		
		ll x = 0;
		for (int i = 0; i < len(A1); i++) {
			A1[i].S += x;
			A2.pb(Mp(A1[i].F, A1[i].S / 2));
			x = (A1[i].S % 2);
		}
		
		sort(all(A2));
		ll ans = 0; x = 0;
		for (int i = len(A2) - 1; i >= 0; i--) {
			while (x > 0 && A2[i].S > 0) {
				if (x == 0) {
					ans += A2[i].F; x = k;
				}
				ll w = min(A2[i].S, x);
				x -= w; A2[i].S -= w;
			}
			ll t = A2[i].S / k;
			ans += A2[i].F * t; A2[i].S -= k * t;
			while (A2[i].S > 0) {
				if (x == 0) {
					ans += A2[i].F; x = k;
				}
				ll w = min(A2[i].S, x);
				x -= w; A2[i].S -= w;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}