#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
const int N = 1e5+10;
struct Node{
    int c;
    int w;
    ll f;
}node[N];
//̰\xd0ĵ\xd8ѡ\xb8\xdf¥\xb2\xe3\xb5\xc4\xcb\xcd
bool cmp1(Node &a,Node &b){
    return a.f<b.f;
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>node[i].c>>node[i].w>>node[i].f;
    }
    sort(node+1,node+n+1,cmp1);
    ll ans=0;
    pair<ll,ll> left={node[n].f,0};//<\xb8߶\xc8,ʣ\xd3\xe0\xc1\xbf>
    for(int i=n;i>=1;i--){
        ll sum=(ll)node[i].c*node[i].w;
//        cout<<sum<<endl;
        if(left.second>0){//\xb4\xa6\xc0\xedǰ\xc3\xe6\xd2\xc5\xc1\xf4֮\xce\xef
            if(left.second+sum<k){//\xb1\xbe\xb2㲻\xd0\xe8Ҫ\xb6\xee\xcd\xe2\xcb\xcd
                left.second+=sum;
                continue;
            }else{
                ans+=(ll)left.first;
                sum-=(k-left.second);
                left.second=0;
            }
        }
        //\xb4\xa6\xc0\xed\xb1\xbe\xb2\xe3֮\xce\xef
        ll x=sum/k,y=sum%k;
        ans+=(ll)x*node[i].f;
        left.first=node[i].f,left.second=y;
//        cout<<ans<<endl;
//        cout<<"-----------"<<endl;
    }
    if(left.second>0){
    	ans+=left.first;
	}
    cout<<ans<<endl;

}
int main(){
    int t;
    cin>>t;
//t=1;
    while(t--){
        solve();
    }
}