#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 N=1e5+10;
typedef struct node{
    i64 c,w,f;
    
}node;
node  q[N];
bool cmp(node a,node b){
     return a.f<b.f;
}
void solve()
{
    i64 n,k;
    i64 sum[N]={0};
    cin>>n>>k;
    for(i64 i=1;i<=n;i++) cin>>q[i].c>>q[i].w>>q[i].f;
    sort(q+1,q+1+n,cmp);
    for(i64 i=1;i<=n;i++)
        if((q[i].w==1))
        sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    i64 qqq=0;
    for(i64 i=1;i<=n;i++){
        if(q[i].w==1) qqq=i;
    }
    i64 ans=0;
    for(i64 i=n;i>=1;i--){
        if(q[i].c*q[i].w>=k){
            ans+=q[i].f*(q[i].c*q[i].w/k);
            q[i].c%=k/q[i].w;
        }
        if(q[i].c==0) continue;
        i64 res=k;
        ans+=q[i].f;
        i64 j=i;
        while(1){
            if(q[j].c*q[j].w<res) res-=q[j].c*q[j].w,q[j].c=0;
            else {
                q[j].c-=res/q[j].w,res%=q[j].w;
                break;
            }
            j--;
            if(j==0) break;
        }
        if(j==0) break;
        qqq=min(qqq,j);
        if(res){
            if(sum[qqq]==0) continue;
            i64 l=1,r=qqq;
            while(l<r){
                i64 mid=l+r>>1;
                if(sum[mid]==sum[j]) r=mid;
                else l=mid+1;
            }
            qqq=l;
            q[qqq].c--;
            if(q[qqq].c==0) qqq--;
        }
    }
    cout<<ans<<endl;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    i64 T = 1;
    cin >> T;
    while (T--)
        solve();

    return 0;
}