#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read() {
    ll x=0, f=1; char ch=' ';
    while(!isdigit(ch)) { ch=getchar(); if(ch=='-') f=-1; }
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-48), ch=getchar();
    return x*f;
}
ll n, k;
struct AB{
    ll c, w, f;
    bool operator < (const AB &A) const{
        return f > A.f;
    }
}a[100005];
void solve() {
    n=read(), k=read();
    for(int i=1;i<=n;i++) {
        a[i].c=read(), a[i].w=read(), a[i].f=read();
    }
    sort(a+1, a+n+1);
    ll now=1, res=k, h=0, ans=0;
    for(int i=1;i<=n;i++) {
        while((now<=i||a[now].w!=1||a[now].c==0)&&now<=n) now++;
        if(!a[i].c) continue;
        h=max(h, a[i].f);
        if(res>=a[i].c*a[i].w) {
            res-=a[i].c*a[i].w;
            continue;
        }
        a[i].c-=res/a[i].w, res-=res/a[i].w*a[i].w;
        if(res&&now<=n) a[now].c--;
        ans+=h;
        ans+=a[i].c*a[i].w/k*a[i].f;
        if(a[i].c*a[i].w%k==0) res=k, h=0;
		else res=k-a[i].c*a[i].w%k, h=a[i].f;
    }
    ans+=h;
    printf("%lld\n", ans);
}
int main() {
    int t=read();
    while(t--) solve();
}