#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
ll k;
vector<array<int, 2>> ve;// num: c  floor: f
vector<int> rems;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        ve.clear(), rems.clear();
        for (int i = 1; i <= n; i++) {
            int c, w, f;
            cin >> c >> w >> f;
            if (w == 2) ve.push_back({c, f});
            else {
                if (c > 1) ve.push_back({c / 2, f});
                if (c & 1) rems.push_back({f});
            }
        }
        sort(rems.begin(), rems.end(), greater<int>());
        for (int i = 0; i < (int)rems.size(); i += 2) {
            ve.push_back({1, rems[i]});
        }
        sort(ve.begin(), ve.end(), [&](auto x, auto y) {
            return x[1] > y[1];
        });
        ll m = k / 2;
        ll ans = 0, res = 0;
        for (auto [c, f] : ve) {
            if (c <= res) {
                res -= c;
                continue;
            }
            c -= res;
            res = 0;
            ll cnt = (c + m - 1) / m;
            ans += cnt * f;
            res = (m - (c % m)) % m;
        }
        cout << ans << "\n";
    }
}