#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<pair<int, int>, int, greater<pair<int, int>>> mp;
    for (int i = 0; i < n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        mp[{f, w}] += c;
    }
    map<pair<int, int>, int, greater<int>>::iterator ite = mp.begin();
    int ans = 0, last = k, nowf = 0;
    for (map<pair<int, int>, int, greater<int>>::iterator it = mp.begin();
         it != mp.end(); it++) {
        auto l = (*it).first;
        auto r = (*it).second;
        ite = it;
        // cerr << ans << ' ' << nowf << ' ' << last << '\n';
        if (l.second == 2) {
            if (r * 2 < last) {
                last -= r * 2;
                nowf = max(nowf, l.first);
            } else if (r * 2 == last) {
                last = k, nowf = max(nowf, l.first), ans += nowf, nowf = 0;
            } else {
                if (last & 1) {
                    while (ite != mp.end() && (*ite).first.second != 1 &&
                           ((*ite).first.second == 1 && (*ite).second == 0)) {
                        ite++;
                    }
                    if (ite != mp.end()) (*ite).second--, last--;
                }
                r -= last / 2;
                nowf = max(nowf, l.first), ans += nowf;
                last = k, nowf = l.first;
                ans += nowf * (r / (last / 2));
                r = r % (last / 2);
                last -= r * 2;
                if (last == k) nowf = 0;
            }
        } else {
            if (r == 0) {
                continue;
            }
            if (r < last) {
                last -= r;
                nowf = max(nowf, l.first);
            } else if (r == last) {
                last = k, nowf = max(nowf, l.first), ans += nowf, nowf = 0;
            } else {
                r -= last;
                nowf = max(nowf, l.first), ans += nowf;
                last = k, nowf = l.first;
                ans += nowf * (r / (last)), r = r % (last);
                last -= r;
                if (last == k) nowf = 0;
            }
        }
    }
    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();
    }
}