#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>, greater<int>> mp;
    int minn = LLONG_MAX;
    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;
        minn = min(minn, f);
    }
    int ans = 0, last = k, nowf = 0;
    bool tag = 0;
    for (auto &it : mp) {
        if (tag) {
            it.second.first--;
        }
        // cerr<<it.first<<'\n';
        if (it.second.second) {
            if (last >= it.second.second) {
                last -= it.second.second;
                nowf = max(nowf, it.first);
            } else {
                if (last & 1) {
                    if ((it.second.first == 0 && it.first != minn) ||
                        it.second.first > 0) {
                        it.second.first--;
                    }
                    last--;
                }
                it.second.second -= last;
                nowf = max(nowf, it.first);
                ans += nowf;
                nowf = it.first;
                ans += it.second.second / k * it.first;
                it.second.second = it.second.second % k;
                last = k - it.second.second;
            }
        }
        if (it.second.first < 0) {
            it.second.first++;
            tag = 1;
        }
        if (it.second.first) {
            if (last >= it.second.first) {
                last -= it.second.first;
                nowf = max(nowf, it.first);
            } else {
                it.second.first -= last;
                nowf = max(nowf, it.first);
                nowf = it.first;
                ans += nowf;
                ans += it.second.first / k * it.first;
                it.second.first = it.second.first % k;
                last = k - it.second.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();
    }
}