#include <bits/stdc++.h>

using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using i64 = long long;
using i128 = __int128;

void solve() {
    int n;
    i64 k;
    cin >> n >> k;
    vector<array<i64, 3>> a(n);
    for (auto &[f, w, cnt] : a) {
        cin >> cnt >> w >> f;
        if (w == 2) cnt <<= 1;
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    i64 ans = 0;
    i64 pos = 0;
    for (auto [f, w, cnt] : a) {
        ans += ((pos + cnt + k - 1) / k - (pos + k - 1) / k) * f;
        pos += cnt;
    }
    cout << ans << '\n';
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int Case; 
    cin >> Case;
    while (Case --) solve();
    return 0;
}