#include<iostream>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
int T, n, k, R, sum[N];
struct par{
	int c;
	int w;
	int f;
}pars[N];
bool cmp(par A, par B){ 
	return A.f < B.f; 
}

signed main() {
	scanf("%lld", &T);
	while(T--) {
		R = 0;
		scanf("%lld %lld", &n, &k);
		for(int i = 1; i <= n; i++) {
			scanf("%lld %lld %lld", &pars[i].c, &pars[i].w, &pars[i].f);
		}
		sort(pars + 1, pars + n + 1, cmp);
		for(int i = 1; i <= n; i++) {
			sum[i] = sum[i - 1] + (pars[i].w == 1);
			if(pars[i].w == 1) R = i;
		}
		int ans = 0;
		for(int i = n; i >= 1; i--) {
			if(pars[i].w * pars[i].c >= k){
				ans += pars[i].f * ((pars[i].w * pars[i].c) / k);
				pars[i].c %= k / pars[i].w;
			}
			if(!pars[i].c) continue;
			int now = k;
			int j = i;
			ans += pars[i].f;
			while(1) {
				if(pars[j].w * pars[j].c < now){
					now -= pars[j].w * pars[j].c;
					pars[j].c = 0;
				}
				else {
					pars[j].c -= now / pars[j].w; 
					now %= pars[j].w; 
					break; 
				}
				j--;
				if(j == 0) break;
			}
			if(j == 0) break;
			R = min(j, R);
			if(sum[R] == 0 || now == 0) continue;
			
			int l = 1, r = R, mid, res;
			while(l <= r) {
				mid = l + r >> 1;
				if(sum[mid] == sum[j]){
					res = mid;
					r = mid - 1;
				}
				else l = mid + 1;
			}
			
			
			R = res;
			pars[R].c--;
			if(!pars[R].c) R--;
		}
		printf("%lld\n", ans);
	}
	return 0;
}