#include<bits/stdc++.h>
using namespace std;
struct node{
	long long w,f,c;
};

bool cmp(node a,node b){
	return a.f<b.f;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long t;
	cin>>t;
	for(long long asd=0;asd<t;asd++){
		long long n,k;
		cin>>n>>k;
		vector<node>all(n),fard,zog;
		for(long long i=0;i<n;i++){
			cin>>all[i].c>>all[i].w>>all[i].f;
			if(all[i].w==1){
				fard.push_back(all[i]);
			}
			else{
				zog.push_back(all[i]);
			}
		}
		sort(fard.begin(),fard.end(),cmp);
		for(long long i=(long long)fard.size()-1;i>=0;i--){
			if(fard[i].c%2==0){
				fard[i].c/=2;
				zog.push_back(fard[i]);
			}
			else{
				fard[i].c++;
				fard[i].c/=2;
				zog.push_back(fard[i]);
				if(i!=0){
					fard[i-1].c--;
				}
			}
		}
		k/=2;
		sort(zog.begin(),zog.end(),cmp);
	//	for(long long i=0;i<(long long)zog.size();i++){
	//		zog[i].c/=2;
	//	}
		long long now=0,res=0;
		while((long long)zog.size()>0){
		//	cout<<res<<" "<<zog.back().c<<" "<<zog.back().w<<" "<<zog.back().f<<" "<<now<<endl;
			if(zog.back().c<=now){
				now-=zog.back().c;
				zog.pop_back();
				continue;
			}
			else if(now!=0){
				zog.back().c-=now;
				continue;
			}
			if(zog.back().c>=k){
				res+=zog.back().f*(zog.back().c/k);
				zog.back().c%=k;
				continue;
			}
			res+=zog.back().f;
			now=k-zog.back().c;
			zog.pop_back();
		}
		cout<<res<<"\n";
	}
}