#include <bits/stdc++.h>
using namespace std;
int t, n, m, k, tot;
struct node {
    int c, w, h;
} a[200005];
struct Node {
    int one, two, f;
} b[200005];
bool cmp(node a, node b) { return a.h > b.h; }
void zhuang(int id, int k) {
    // cout << id << ' ' << k << '\n';
    if (k == 0 || id > tot) return;
    if (2ll * b[id].two + b[id].one <= k) {
        zhuang(id + 1, k - 2ll * b[id].two - b[id].one);
        b[id].two = 0;
        b[id].one = 0;
    } else {
        int num = k / 2;
        k -= 2ll * min(b[id].two, num);
        if (num >= b[id].two)
            b[id].two = 0;
        else
            b[id].two -= num;
        if (k > 0) {
            int num = k;
            k -= min(b[id].one, num);
            if (num >= b[id].one)
                b[id].one = 0;
            else
                b[id].one -= num;
        }
        zhuang(id + 1, k);
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i].c >> a[i].w >> a[i].h;
        sort(a + 1, a + 1 + n, cmp);
        tot = 0;
        int one = 0, two = 0;
        for (int i = 1; i <= n; i++)
            if (i == n || a[i].h != a[i + 1].h) {
                tot++;
                if (a[i].w == 1)
                    one += a[i].c;
                else
                    two += a[i].c;
                b[tot].one = one;
                b[tot].two = two;
                b[tot].f = a[i].h;
                one = 0;
                two = 0;
            } else {
                if (a[i].w == 1)
                    one += a[i].c;
                else
                    two += a[i].c;
            }
        int ans = 0;
        // cout << tot << '\n';
        // for (int i = 1; i <= tot; i++) cout << b[i].one << ' ' << b[i].two << ' ' << b[i].f <<
        // '\n';
        for (int i = 1; i <= tot; i++) {
            if (b[i].one == 0 && b[i].two == 0) continue;
            if (b[i].two * 2 >= k) {
                int num = b[i].two / (k / 2);
                ans += b[i].f * num;
                b[i].two -= k / 2 * num;
                i--;
                continue;
            }
            if (b[i].two == 0 && b[i].one >= k) {
                int num = b[i].one / k;
                ans += b[i].f * num;
                b[i].one -= num * k;
                i--;
                continue;
            }
            if (b[i].two * 2 + b[i].one >= k) {
                ans += b[i].f;
                b[i].two = 0;
                int x = k - 2ll * b[i].two;
                b[i].one -= x;
                i--;
                continue;
            }
            zhuang(i, k);
            ans += b[i].f;
            // cout << i << ' ' << ans << '\n';
        }
        cout << ans << '\n';
    }
}