#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;

int n,m;
struct node{
    int a,b,c;
} p[N];
bool cmp(node a,node b){
    return a.c>b.c;
}

void solve() {
    //int sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].a>>p[i].b>>p[i].c;
        //sum+=p[i].a*p[i].b;
    }
    int res=0;
    sort(p+1,p+1+n,cmp);
    vector<node> one;
    vector<int> id;
    for(int i=1;i<=n;i++)
    {
       //res+=(p[i].a*p[i].b)/m*p[i].c;
       //p[i].a=((p[i].a*p[i].b)%m)/p[i].b; 
       if(p[i].b==1) 
       {
         one.push_back(p[i]);
         id.push_back(i);
       }
       //else two.push_back(p[i]);           
    }
    //cout<<res<<endl;
    int j=0;
    int sum1=one.size();
    int i=1;
    while(i<=n)
    {
        res+=(p[i].a*p[i].b)/m*p[i].c;
        p[i].a=((p[i].a*p[i].b)%m)/p[i].b; 
        if(p[i].a==0)
        {
            i++;
            continue;
        }
        res+=p[i].c;int temp=0; 
        while(i<=n&&temp+p[i].a*p[i].b<=m) 
        {
            temp+=p[i].a*p[i].b;
            p[i].a=0;
            i++;
        }
        if(i>n) break;
        int t=(m-temp)/p[i].b;
        temp+=p[i].b*t; 
        p[i].a-=t;
        if(temp<m)
        {
            while(j<sum1&&p[id[j]].a==0) j++;
            if(j<sum1) p[id[j]].a--; 
        }  
    }
    cout<<res<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}