#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
#define int ll

const int N=1e5+100;

struct Item
{
    int f,w,c;
    friend auto operator<=>(const Item&, const Item&)=default;
} items[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>items[i].c>>items[i].w>>items[i].f;
        sort(items+1,items+n+1,greater<>());
        int ans=0,left=0;
        bool one=false;
        for(int i=1;i<=n;i++)
        {
            auto[f,w,c]=items[i];
            if(w==1&&one)
                c--,one=false;
            int take=min(c,left/w);
            c-=take;
            left-=take*w;
            if(!c)
                continue;
            if(left)
                one=true,
                left=0;
            int times=c*w/k;
            ans+=f*times;
            c-=times*k/w;
            if(!c)
                continue;
            ans+=f;
            left=k-c*w;
        }
        cout<<ans<<"\n";
    }
}