#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
//#define endl '\n'

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
const int mod1e9 = 1e9 + 7;
const int mod998 = 998244353;
int n,m,k,q,ans,x,y,z,d,c,w,f;


void solve() {
	cin >> n >> k;
	priority_queue<array<int,2>,vector<array<int,2>>,less<array<int,2>>> pr;
	for(int i = 1;i <= n;i ++) {
		cin >> c >> w >> f;
		pr.push({f,c * w});
	}
	int ans = 0;
	int empty = 0;
	while(pr.size()) {
		auto [f,value] = pr.top();
		pr.pop();
		if(value <= empty) {
			empty -= value;
			continue;
		}
		value -= empty;
		empty = 0;
		int need = value / k;
		ans += need * f;
		//cout << need << " " << value << endl;
		if(value % k > 0) {
			empty = k - value % k;
			ans += f;
		}
	}
	cout << ans << endl;
	
}


signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	int t = 1; 
	cin >> t;
	for(int i = 1;i <= t;i ++) 
	solve();
	return 0;
}