#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3+10,M=2e4+10,mod = 998244353;
struct Node
{
    int x,y;
    bool operator < (const Node &W)const
    {
        return x>W.x;
    };
};
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>c(n+1,0),w(n+1,0),f(n+1,0);
    set<Node>st;
    vector<Node>nums;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>w[i]>>f[i];
        if(w[i]==1) st.insert({f[i],i});
        nums.push_back({f[i],i});
    }
    sort(nums.begin(),nums.end());
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t =nums[i].x,p=nums[i].y;
        if(!c[p])   continue;
        int sum=0;
        int j=i;
        while(j<n)
        {
            int pj = nums[j].y;
            if(sum+w[pj]*c[pj]>k)   break;
            sum+=w[pj]*c[pj];
            c[pj]=0;
            if(w[pj]==1&&st.count(nums[j]))    st.erase(nums[j]);
            j++;
        }
        if(j<n)
        {
            int pj = nums[j].y;
            int x = (k-sum)/w[pj];
            c[pj]-=x,sum+=x*w[pj];
            if(k-sum==1&&st.size())
            {
                auto it = *st.begin();
                c[it.y]--;
                if(!c[it.y])    st.erase(it);
            }
            x = c[pj]*w[pj]/k;
            ans+=x*f[pj];
            c[pj]-=x*(k/w[pj]);
            if(!c[pj])
            {
                if(w[pj]==1)    st.erase(nums[j]);
                j++;
            }
        }
        
        ans+=t;
        i=j-1;
    }
    
    cout<<ans<<"\n";
}



signed main()
{
    int T=1;
    cin.tie(0)->sync_with_stdio(false);
    cin>>T;
    //init();
    while(T--)
    {
        solve();
    }
    return 0;
}