#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
//#define int long long
const int N = 5e5 + 50;
const int M = 2005;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

struct node {
	ll num, c, h;
}mp[N];

int cmp(node a, node b) {
	if (a.h > b.h)return 1;
	if (a.h == b.h && a.c > b.c)return 1;
	return 0;
}


void solve()
{
	//感觉就是一个小模拟
	//还有就是，如果为偶数，先奇先偶无所谓
	//但是如果m为奇数，应该先消耗偶数，不然奇数不能被充分利用
	//除此之外似乎就没有了
	queue<ll>q;
	ll n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> mp[i].num >> mp[i].c >> mp[i].h;
	}
	sort(mp + 1, mp + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		if (mp[i].c == 1)q.push(i);
	}
	ll ans = 0;
	ll ex = 0;
	ll base = mp[1].h;
	for (int i = 1; i <= n; i++) {
		ll num = mp[i].num, c = mp[i].c, h = mp[i].h;
		base = max(base, h);
		if (num * c + ex >= m) {
			//先凑出一次
			ans += base; base = h;
			ll dis = m - ex;
			if (dis % c == 1) {
				if (q.size()) {
					ll pos = q.front();
					mp[pos].num--;
					if (mp[pos].num == 0)q.pop();
					num -= (dis / c);
				}
			}
			else {
				num -= dis / c;
			}
			//再一把一把的出
			if (m % c == 1) {
				while (1) {
					if (q.empty()) {
						ans += (base * (num * c / (m - 1)));
						ex = num * c % (m - 1); break;
					}
					if (num == 0) {
						base = 0;
						ex = num * c % (m - 1); break;
					}
					ll pos = q.front();
					ll nn = mp[pos].num, hh = mp[pos].h;
					ll nnn = (num * c / (m - 1));
					mp[pos].num -= min(nn, nnn);
					num -= min(nn, nnn) * (m - 1) / c;
					if (mp[pos].num == 0)q.pop();
				}
			}
			else {
				ex = (num * c) % m;
				ans += (base * (num * c / m));
			}

		}
		else {
			base = max(base, h);
			ex += (num * c);
		}
		if (c == 1 && q.size()) {
			if (q.front() == i)q.pop();
		}
		//cout << ans << endl;
	}
	if (ex)ans += base;
	cout << ans << endl;
	return;
}


signed main()
{

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T = 1;
	std::cin >> T;
	while (T--)
		solve();
	return 0;
}


ll ksm(ll a, ll b) {
	ll base = a;
	ll ans = 1;
	while (b) {
		if (b & 1)ans *= base;
		base *= base;
		b >>= 1;
	}
	return ans;
}
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}