#include <stdio.h>
#include <string.h>
#include <assert.h>

#include <vector>
#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)
#define eb emplace_back

using namespace std;

typedef long long LL;
constexpr int N = 100005;

int n; LL m, res;
struct Good {
	int c, w, f;
	bool operator < (const Good &t) const {
		return f < t.f;
	}
} a[N];
LL cnt1, remain;

void work1(int cnt, int cost) {
	assert(remain == 0ll && cnt1 == 0ll);
	LL k = (cnt - 1) / m + 1;
	res += cost * k;
	remain = m * k - cnt;
}

void work2(int cnt, int cost) {
	assert(remain == 0ll);
	LL k = (cnt - 1) / (m / 2) + 1;
	res += cost * k;
	remain = m * k - 2 * cnt;
}

int main() {
	int task;
	for (scanf("%d", &task); task--; ) {
		scanf("%d%lld", &n, &m);
		for (int i = 0; i < n; ++i) {
			auto &[c, w, f] = a[i];
			scanf("%d%d%d", &c, &w, &f);
		}
		sort(a, a + n);
		res = 0ll;
		for (int i = n - 1; ~i; --i) {
			auto &[c, w, f] = a[i];
			LL t = min((LL)c, remain / w);
			remain -= t * w;
			c -= t;
			if (remain == 1) {
				cnt1 += 1;
				remain = 0ll;
			}
			if (w == 1) {
				t = min((LL)c, cnt1);
				c -= t;
				cnt1 -= t;
			}
			if (!c) {
				continue;
			}
			(w == 1 ? work1 : work2)(c, f);
		}
		printf("%lld\n", res);
	}
	return 0;
}