#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

#define int int64_t

void solve() {
    int n, k;
    cin >> n >> k;
    k /= 2;
    vector<array<int, 2>> arr;
    vector<int> solo;
    for (int i = 0; i < n; ++i) {
        int c, w, f;
        cin >> c >> w >> f;
        if (w == 2) {
            arr.push_back({f, c});
        }
        if (w == 1) {
            if (c != 1) {
                arr.push_back({f, c / 2});
            }
            if (c % 2 == 1) {
                solo.push_back(f);
            }
        }
    }
    sort(solo.begin(), solo.end());
    for (int i = (int)solo.size() - 1; i >= 0; i -= 2) {
        arr.push_back({solo[i], 1});
    }
    sort(arr.rbegin(), arr.rend());
    int ans = 0;
    int id = 0;
    while (id < (int)arr.size()) {
        if (arr[id][1] == 0) {
            ++id;
            continue;
        }
        if (arr[id][1] >= k) {
            ans += arr[id][0] * (arr[id][1] / k);
            arr[id][1] %= k;
            continue;
        }
        int f = arr[id][0];
        int sz = k;
        for (int i = id; i < (int)arr.size() && sz != 0; ++i) {
            int mn = min(sz, arr[i][1]);
            sz -= mn;
            arr[i][1] -= mn;
        }
        ans += f;
    }
    cout << ans << "\n";
}

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

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}