#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define int long long
#define lowbit(x) x&-x
const int N=1e7+1,mod=1e9+19;
struct node{
    int c,w,f;
    bool operator <(const node p){
        if(f==p.f)return w>p.w;
        else return f>p.f;
    }
};
void solve(){
    int n,k;cin>>n>>k;
    vector<node>a(n);
    for(auto &[c,w,f]:a)cin>>c>>w>>f;
    sort(a.begin(),a.end());
    int ans=0;
    int p=k,cnt=0,ex=0;
    for(auto &[c,w,f]:a){
        c=c*w;
        if(w==1){
            if(c<=ex){
                ex-=c;continue;
            }else c=c-ex,ex=0;
        }
        if(c>=p){
            if(p%w)++ex;
            c-=p/w*w;
            ans+=cnt+c/k*f;
            p=k-c%k;
            if(p)cnt=f;
            else cnt=0;
        }else p-=c;
        cnt=max(cnt,f);
    }
    if(p!=k)ans+=cnt;
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}