#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5 + 5;

int T, n, c[N], w[N], f[N];
i64 k;

void solve() {
	std::cin >> n >> k; std::map<int, i64> M;
	for (int i = 1; i <= n; i++) std::cin >> c[i] >> w[i] >> f[i], M[f[i]] += 1ll * c[i] * w[i];
	std::set<std::array<i64, 2>> S;
	for (auto [x, c] : M) S.insert({x, c});
	i64 ans = 0;
	while (!S.empty()) {
		auto [x, c] = *--S.end();
		if (c >= k) {
			ans += c / k * x;
			c %= k;
		}
		S.erase(--S.end());
		if (c == 0) continue;
		if (S.empty()) {
			ans += x;
			break;
		}
		while (1) {
			if (S.empty()) {
				ans += x;
				break;
			}
			auto [_, d] = *--S.end();
			if (c + d < k) {
				S.erase(--S.end());
				c += d;
			}
			else {
				i64 r = k - c;
				S.erase(--S.end());
				if (d != r) S.insert({_, d - r});
				ans += x;
				break;
			}
		}
	}
	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> T;
	while (T--) solve();

	return 0;
}