#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 solve() {
    int n;
    i64 k;
    cin >> n >> k;
    
    map<int, i64> mp[2];
    for(int i = 0, c, w, f; i < n; i ++) {
        cin >> c >> w >> f;
        mp[w - 1][f] += c;
    }
    for(auto it = mp[0].rbegin(); it != mp[0].rend(); it ++) {
        mp[1][it->first] += (it->second + 1) / 2;
        if(it->second & 1) {
            if(next(it) != mp[0].rend()) next(it)->second --;
        }
    }
    vector v(mp[1].begin(), mp[1].end());
    i64 rem = 0, ans = 0;
    while(v.size()) {
        auto [h, c] = v.back();
        v.pop_back();
        if(rem) {
            i64 cap = min(rem, c);
            rem -= cap;
            c -= cap;
        }
        if(c) {
            ans += h * (c / (k / 2));
            c -= c / (k / 2) * (k / 2);
        }
        if(c) {
            ans += h;
            rem = k / 2 - c;
        }
    }
    return ans;
}

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

    int T;
    cin >> T;
    while(T --) {
        cout << solve() << "\n";
    }
}