#include<bits/stdc++.h>
#define ll long long
const int maxn = 1e5 + 5;
using namespace std;
int n, T;
ll k, ans;
struct node{
    int c, w, f;
    bool operator<(const node &x)const{
        if(f != x.f) return f > x.f;
        else if(w != x. w) return w > x.w;
        else return c > x.c;
    }
}st[maxn];
set<int> one, zero;
void add(int x, int w){
    if(w == 1) one.insert(x);
    else zero.insert(x);
}
void del(int x, int w){
    if(w == 1) one.erase(x);
    else zero.erase(x);
}
int main(){
    scanf("%d",&T);
    for (; T; T--){
        scanf("%d %lld",&n, &k);ans = 0;
        one.clear();zero.clear();
        for (int i = 1; i <= n; i++)
            scanf("%d %d %d",&st[i].c, &st[i].w, &st[i].f);
        sort(st + 1, st + n + 1);
        for (int i = 1; i <= n; i++)
            add(i, st[i].w);
        while(one.size() > 0 || zero.size() > 0){
            int l = n + 1;
            if(one.size() > 0) l = min(l, *one.begin());
            if(zero.size() > 0) l = min(l, *zero.begin());
            if(1LL * st[l].c *st[l].w > k){
                ll cnt = 1LL * st[l].c * st[l].w / k;
                st[l].c -= (k / st[l].w) * cnt; ans += 1LL * cnt * st[l].f;
            }
            if(st[l].c <= 0)del(l, st[l].w);
            if(st[l].c <= 0) continue;
            ll res = k - 1LL * st[l].c * st[l].w;del(l, st[l].w);
            while(1){
                if(one.size() == 0 && zero.size() == 0) break;
                if(res == 0) break;
                if(res == 1 && one.size() == 0)break;
                if(one.size() > 0 && zero.size() > 0){
                    int r = min(*one.begin(), *zero.begin());
                    int num = min(1LL*st[r].c, res / st[r].w);
                    st[r].c -= num, res -= 1LL* num * st[r].w;
                    if(!st[r].c)del(r, st[r].w);
                }
                else if(one.size() > 0){
                    int r = *one.begin();
                    int num = min(1LL*st[r].c, res / st[r].w);
                    st[r].c -= num, res -= 1LL* num * st[r].w;
                    if(!st[r].c)del(r, st[r].w);
                }
                else {
                    int r = *zero.begin();
                    int num = min(1LL*st[r].c, res / st[r].w);
                    st[r].c -= num, res -= 1LL* num * st[r].w;
                    if(!st[r].c)del(r, st[r].w);
                }
            }
            ans += st[l].f;
        }
        printf("%lld\n", ans);
    }
    return 0;
}