#include<bits/stdc++.h>
using namespace std;
#define time chrono::system_clock::now().time_since_epoch().count()
mt19937_64 rnd(time);
#define maxn 1000005
#define int long long

int read() {int x;cin>>x;return x;}

struct node {
    int f, c;
};
bool operator<(node a, node b) {
    return a.f < b.f;
}

void solve() {
    int n = read(), k = read();
    priority_queue<node>q1, q2;
    for(int i = 1; i <= n; i++) {
        int c = read(), w = read(), f = read();
        if(w == 1) q1.push({f, c});
        else q2.push({f, c});
    }
    int ans = 0, las = 0;
    while(q1.size() || q2.size()) {
        node u1, u2;
        if(q1.size()) u1 = q1.top();
        if(q2.size()) u2 = q2.top();
        // cout << ans << " " << las << " " << u1.c << " " << u2.c << "\n";
        if(q1.size() == 0) {
            q2.pop();
            int num1 = (las) / 2;
            if(num1 >= u2.c) {
                las -= u2.c * 2;
                continue;
            }
            u2.c -= num1;
            int val = k / 2;
            int num2 = ((u2.c + val - 1) / val);
            ans += num2 * u2.f;
            las = num2 * k - u2.c * 2;
        }
        else if(q2.size() == 0 || u1.f >= u2.f) {
            q1.pop();
            int num1 = las;
            if(num1 >= u1.c) {
                las -= u1.c;
                continue;
            }
            u1.c -= num1;
            int val = k;
            int num2 = ((u1.c + val - 1) / val);
            ans += num2 * u1.f;
            las = num2 * k - u1.c;
        }
        else {
            q2.pop();
            int num1 = (las) / 2;
            if(num1 >= u2.c) {
                las -= u2.c * 2;
                continue;
            }
            if(las % 2 == 1) {
                q1.pop();
                u1.c -= 1;
                las --;
                if(u1.c > 0) q1.push(u1);
            }
            u2.c -= num1;
            int val = k / 2;
            int num2 = ((u2.c + val - 1) / val);
            ans += num2 * u2.f;
            las = num2 * k - u2.c * 2;
        }
    }
    cout << ans << "\n";
    return;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t = read();
    while(t--) solve();
    return 0;
}