//#pragma GCC target("avx,avx2")
//#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define int long long
#define mem(x,y)memset(x,y,sizeof(x))
#define rep(i,l,r)for(int i = l;i <= r;i ++)
#define dep(i,r,l)for(int i = r;i >= l;i --)
#define tov(i)for(int i = head[x];i;i = e[i].nxt)
#define pb push_back
#define pi pair <int,int> 

using namespace std;

int read(){
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}

namespace Tem{
    const int mod = 0;//Notice Here!!!!!!!!!!
    int fac[1000010],ifac[1000010];

    inline int gcd(int a, int b){
        int az = __builtin_ctz(a);
        int bz = __builtin_ctz(b);
        int z = az > bz ? bz : az;
        int diff;
        b >>= bz;
        while(a){
            a >>= az;
            diff = b - a;
            az = __builtin_ctz(diff);
            if(a < b)b = a;
            a = diff < 0 ? -diff : diff;
        }
        return b << z;
    }

    inline int poww(int x,int y,int MOD = mod){
        int s = 1;
        for(;y;x = x * x % MOD,y >>= 1)if(y & 1)s = s * x % MOD;
        return s;
    }

    void initfac(int n,int MOD = mod){
        fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
        rep(i,2,n)fac[i] = fac[i - 1] * i % MOD;
        ifac[n] = poww(fac[n],MOD - 2,MOD);
        dep(i,n - 1,2)ifac[i] = ifac[i + 1] * (i + 1)% MOD;
    }

    inline int inv(int x,int MOD = mod){return poww(x,MOD - 2)% MOD;}

    inline int C(int x,int y,int MOD = mod){return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;}

    void Add(int &x,int y){x = x + y >= mod ? x + y - mod : x + y;}
    void Dec(int &x,int y){x = x - y < 0 ? x - y + mod : x - y;}
    void Mul(int &x,int y){x = x * y % mod;}
}using namespace Tem;

struct node{
    int c;
    int w;
    int f;
    int d;
}e[1000010],e1[1000010];

int t;
int n,m;
bool bk[1000010];
int nxt[1000010];
int ans;
int d[1000010];

bool cmp(node x,node y){if(x.f != y.f)return x.f > y.f;return x.w > y.w;}

void solve(){
    n = read(),m = read();
    int cnt = 0;
    rep(i,1,n)e[i].c = read(),e[i].w = read(),e[i].f = read(); 
    
    rep(i,1,n)bk[i] = d[i] = 0;
    ans = 0;
    sort(e + 1,e + n + 1,cmp);
    rep(i,1,n - 1){
        if(e[i].f == e[i + 1].f){
            int v = e[i].c * e[i].w;
            if(e[i + 1].w == 1)e[i + 1].c += v;
            else e[i + 1].c += v / 2;
            e[i].c = 0;
        }
    }
    //rep(i,1,n)cout<<"w = "<<e[i].w<<",f = "<<e[i].f<<endl;
    // nxt[n + 1] = n + 1;
    // dep(i,n,1){
    //     if(e[i].w == 2)nxt[i] = nxt[i + 1];
    //     else nxt[i] = i;
    // }
    int now;
   // rep(i,1,n)cout<<"i = "<<i<<",nxt = "<<nxt[i]<<endl;
    rep(i,1,n){
        int v = e[i].c * e[i].w - d[i];
        //cout<<"i = "<<i<<",v = "<<v<<endl;
        if(v <= 0)continue;
        int tt = (v - 1) / m + 1;
        ans += e[i].f * tt;
        now = m - v % m;
        if(now > 0){
            int pos = i + 1;
            while(1){
                d[pos] += now;
                if(e[pos].c * e[pos].w >= now)break;
                now -= e[pos].c * e[pos].w;
                pos ++;
                if(pos > n)break;
            }
        }
    }
    printf("%lld\n",ans);
}

signed main(){
    cin>>t;
    while(t --)solve();
}