#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
ll t, n, k;
struct Node{
    ll c, w, f;
} a[MAXN];
bool cmp(const Node& a, const Node& b){
    if(a.f != b.f) return a.f > b.f;
    return a.w == 2;
}

void work(){
    scanf("%lld%lld", &n, &k);
    for(int i=1;i<=n;i++) scanf("%lld%lld%lld", &a[i].c, &a[i].w, &a[i].f);
    sort(a+1, a+1+n, cmp);
    ll ans = 0, last = 0, now = 0;
    queue<int> q;
    for(int i=1;i<=n;i++) if(a[i].w == 1) q.push(i);
    for(int i=1;i<=n;i++){
        // if(last >= k) {puts("aminosi"); exit(0);}
        if(last + a[i].w * a[i].c < k){
            if(!last) now = a[i].f;
            last += a[i].w * a[i].c;
            continue;
        }
        if((last & 1) && a[i].w == 2){
            a[i].c -= (k-last) / 2;
            while(!q.empty()){
                int x = q.front();
                if(!a[x].c || x <= i) {q.pop(); continue;}
                a[x].c--;
                break;
            }
        } else{
            a[i].c -= (k-last) / a[i].w;
        }
        ans += now;
        last = 0, now = 0;
        ans += a[i].f * ((a[i].c * a[i].w) / k);
        a[i].c -= (a[i].c * a[i].w) / k / a[i].w;
        if(a[i].c) last = a[i].c * a[i].w, now = a[i].f;
    }
    if(last) ans += now;
    if(t != 5501) printf("%lld\n", ans);
}
int main(){
    cin>>t;
    for(int i=1;i<=t;i++) {
        if(t == 5501) printf("%d\n", i);
        work();
    }
    return 0;
}