#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+100;
struct node{
    ll c, w, f;
    bool operator < (node ex){
        if(f == ex.f) return w > ex.w;
        return f > ex.f;
    }
};
ll n, k;
node mes[N];
ll solve(){
    int l = 1, nxt = 1;
    while(nxt <= n && mes[nxt].w != 1) nxt++;
    ll ans = 0;
    while(l <= n){
        ll tot = mes[l].c * mes[l].w;
        ans += tot / k * mes[l].f;
        mes[l].c = (tot % k) / mes[l].w;

        if(!mes[l].c){
            l++; continue;
        }
        
        ll sum = 0;
        int r = l;
        while(r <= n && sum + mes[r].w*mes[r].c <= k){
            sum += mes[r].w * mes[r].c, r++;
        }
        if(r > nxt){
            nxt = r;
            while(nxt <= n && (mes[nxt].w != 1 || !mes[nxt].c)) nxt++;
        }
        if(r == n+1){
            ans += mes[l].f; break;
        }else{
            if(sum % mes[r].w){
                if(nxt <= n) mes[nxt].c--;
                mes[r].c -= (k-1-sum)/mes[r].w;
                if(!mes[nxt].c){
                    nxt++;
                    while(nxt <= n && (mes[nxt].w != 1 || !mes[nxt].c)) nxt++;
                }
                ans += mes[l].f;
            }else{
                mes[r].c -= (k-sum)/mes[r].w, ans += mes[l].f;
            }
        }
        l = r;
    }
    return ans;
}
int main(){
    int t; scanf("%d", &t);
    while(t--){
        scanf("%lld%lld", &n, &k);
        for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &mes[i].c, &mes[i].w, &mes[i].f);
        sort(mes+1, mes+n+1);
        printf("%lld\n", solve());
    }
    return 0;
}