#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+5;
struct node {
	int num,w,f;
}th[N];
bool cmp(node a, node b){
	return a.f > b.f;
}

signed main() {
//	IOS;
	int t,n,k;
	cin>>t;
	while(t--) {
		cin>>n>>k;
		int ans=0,sum=0;
		for(int i=0;i<n;i++) {
			cin>>th[i].num>>th[i].w>>th[i].f;
		}
		sort(th, th+n, cmp);
		for(int i=0;i<n;i++) {
			if(th[i].w*th[i].num>=k) {
				ans+=(th[i].w*th[i].num/k)*th[i].f;
				th[i].num-=k/th[i].w*(th[i].w*th[i].num/k);
			}
		}
		for(int i=0;i<n;i++) {
			if(th[i].num==0) continue;
			if(sum==0) ans+=th[i].f;
			if(sum+th[i].num*th[i].w<=k) {
				sum+=th[i].num*th[i].w;
			}
			else {
				th[i].num-=(k-sum)/th[i].w;
				sum+=(k-sum)/th[i].w*th[i].w;
				
				if(k-sum==1) {
					for(int j=i;j<n;j++) {
						if(th[j].w==1&&th[j].num!=0) {
							sum+=th[j].w;
							th[j].num--;
							break;
						}
					}
				}
				sum=th[i].num*th[i].w;
				ans+=th[i].f;
			}
			sum=sum%k;	
		}
		cout<<ans<<endl;
	}
	return 0;
}
/*
  4
  4 6
  1 1 8
  7 2 5
  1 1 7
  3 2 6
  8 1200000
  100000 1 100000
  100000 1 12345
  100000 2 100000
  100000 2 12345
  100000 1 100000
  100000 1 12345
  100000 2 100000
  100000 2 12345
  4 6
  1 1 8
  1 2 7
  3 2 6
  3 1 5
  12 12
  6 1 2
  1 2 2
  1 1 2
  1 2 4
  6 1 1
  1 2 5
  6 1 4
  4 1 4
  6 2 4
  6 2 5
  4 2 5
  4 1 4
 */