#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int SZ = 101010;

int n; 
ll k, a[2][SZ];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	int T; cin >> T;
	while (T--) {
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			int c, w, f;
			cin >> c >> w >> f;

			a[w - 1][f]	+= c;
		}

		int p = SZ - 1, t = SZ - 1;
		ll ans = 0;
		while (true) {
			ll s = 0;
			int m = -1;
			while (p > 0 && s + a[0][p] + 2 * a[1][p] <= k) {
				ll x = a[0][p] + 2 * a[1][p];
				if (!x) {
					--p; continue;
				}
				s += x;
				if (m == -1) m = p;
				a[0][p] = 0;
				a[1][p] = 0;
				--p;
			}
			if (p == 0) {
				if (m != -1) {
					ans += m;
				}
				break;
			}

			if (m == -1) {
				ll tot = (a[0][p] + 2 * a[1][p]) / k;
				ans += p * tot;

				ll r = (a[0][p] + 2 * a[1][p]) % k;
				if (a[0][p] > r) {
					a[0][p] = r;
					a[1][p] = 0;
				}
				else {
					a[1][p] = (r - a[0][p]) / 2;
				}
			}
			else {
				if (s & 1) {
					while (t > 0 && a[0][t] == 0) {
						--t;
					}
					if (t != 0) {
						a[0][t]--;
						++s;
					}
				}
				if (2 * a[1][p] >= k - s) {
					a[1][p] -= (k - s) / 2;
					s += (k - s);
				}
				else {
					s += 2 * a[1][p];
					a[1][p] = 0;
					a[0][p] -= (k - s);
				}
				ans += m;
			}
		}
		cout << ans << '\n';

		for (int i = 0; i < SZ; i++) {
			a[0][i] = a[1][i] = 0;
		}
	}
}