#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

void solve() {
    ll n, k; cin >> n >> k;
    vector<tuple<ll, ll, ll>> a(n);
    for (int i = 0; i < n; ++i) {
        ll c, w, f; cin >> c >> w >> f;
        a[i] = {f, w, c};
    }
    sort(a.rbegin(), a.rend());
    ll cnt[3]{}, ans = 0;
    for (int i = 0; i < n; ++i) {
        auto[f, w, c] = a[i];
        if (w == 2) {
            ll t = min(cnt[2], c);
            cnt[2] -= t, c -= t;
            if (c) {
                ll d = c * 2 / k, r = c * 2 % k;
                ans += d * f;
                if (r) ans += f, r = k - r;
                cnt[2] += r / 2;
            }
        } else {
            ll t = min(cnt[1], c);
            cnt[1] -= t, c -= t;
            t = min(cnt[2], (c + 1) / 2);
            cnt[2] -= t, c -= t * 2;
            if (c == -1) ++cnt[1];
            if (c > 0) {
                ll d = c / k, r = c % k;
                ans += d * f;
                if (r) ans += f, r = k - r;
                cnt[1] += r & 1, cnt[2] += r / 2;
            }
        }
    }
    cout << ans << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}