#include<bits/stdc++.h>
const int N = 100005;
using namespace std;

struct bags{
	long long c, w, f;
	bool operator <(const bags &o)const{
		return f>o.f;
	}
}bag[N];

int n;
long long k;

void real_main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin >> bag[i].c >> bag[i].w >> bag[i].f;
	}
	sort(bag+1, bag+1+n);
	
	long long ans = 0 ;
	
	long long now = 1;            // 现在处理到第几组包裹
	queue<int> q;
	
	for(int i=1;i<=n;i++){
		if(bag[i].w == 1){
			q.push(i);
		}
	}
	
	while(now<=n) {
		
		if(bag[now].c * bag[now].w >= k){  // 全部处理当前组 
			long long times = bag[now].c * bag[now].w / k;  // 完整处理几次
			ans += times * bag[now].f; 
			bag[now].c -= times * k / bag[now].w;
			while (bag[now].c == 0 && now <= n){
				now++;
			} 
		} else {  // 当前组只占部分空间便处理完成 剩余空间分给后面的组 
			ans += bag[now].f;
			long long now_k = k - bag[now].c * bag[now].w;
			now++;
			while(now_k - bag[now].c * bag[now].w >= 0 && now <= n){  // 能整组吃掉 
				now_k -= bag[now].c * bag[now].w;
				now ++;
			}
			
			if(now>n) break;
			
			if(now_k%2==1){
				while(q.size()&&q.front()<now) q.pop();
				while(q.size()&&bag[q.front()].c <= now_k){  // 整组吃掉 w = 1 的 
					bag[q.front()].c = 0;
					now_k -= bag[q.front()].c;
					q.pop();
				}	
				if(q.size()){
					bag[q.front()].c -= now_k;
				}
			} else {
				bag[now].c -= now_k / bag[now].w;
			}
		}
		
	}
	cout<<ans<<endl; 
}

int main(){
	int T;
	for(cin>>T;T;T--){
		real_main();
	}
	return 0;
}