#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int MX=100010;

int T, N, K;
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
struct node
{
    int c, w, f;
    bool operator < (const node &a)const{
        return f>a.f;
    }
}ar[MX];
signed main()
{
    // freopen("testdata.in","r",stdin);
    T=read();
    while(T--)
    {
        N=read(); K=read();
        for(int i=1;i<=N;i++)
        {
            int c=read(), w=read(), f=read();
            c*=w;
            ar[i]={c,w,f};
        }
        sort(ar+1,ar+1+N);
        int ans=0, res=0, val=0;
        for(int i=1;i<=N;i++)
        {
            auto [c,w,f]=ar[i];
            // cout << "c=" << c << ", w=" << w << ", f=" << f << '\n';
            if(res==0) val=f;
            res+=c;
            if(res>=K) 
            {
                ans+=val; res-=K;
                if(!res) continue;
                val=f;
                ans+=res/K*val, res%=K;
            }
        }
        if(res) ans+=val;
        cout << ans << '\n';
    }
    return (0-0);
}