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

struct node {
    int c, w, f;
};
void solve() {
    int n, k;
    cin >> n >> k;
    map<int, pair<int, int>, less<int>> mp;
    for (int i = 0; i < n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        if (w == 1)
            mp[f].first += c;
        else
            mp[f].second += c * 2;
    }
    int ans = 0, last = k, nowf = 0;
    for (auto &it : mp) {
        if (last > it.second.second) {
            last -= it.second.second;
            nowf = max(nowf, it.first);
        } else {
            // if (last & 1) {
            //     it.second.first--;
            //     last--;
            // }
            it.second.second -= last;
            nowf = max(nowf, it.first);
            ans += nowf;
            ans += it.second.second / k * it.first;
            it.second.second = it.second.second % k;
            last = k - it.second.second;
            nowf = max(nowf, it.second.first);
        }
        // if (it.second.first < 0) {
        // }
        if (last > it.second.first) {
            last -= it.second.first;
            nowf = max(nowf, it.first);
        } else {
            it.second.first -= last;
            nowf = max(nowf, it.first);
            ans += nowf;
            ans += it.second.first / k * it.first;
            it.second.first = it.second.first % k;
            last = k - it.second.first;
            nowf = max(nowf, it.first);
        }
    }
    if (last != k) {
        ans += nowf;
    }
    cout << ans << '\n';
    return;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}