#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n, m;
    cin >> n >> m;
    priority_queue<pair<int, int>> q1, q2;
    for (int i = 1; i <= n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        if (w == 1)
            q1.push({f, c});
        else
            q2.push({f, c});
    }
    int ans = 0;
    int k = 0;
    while (!q1.empty() || !q2.empty()) {
        if (k == 0) {
            if (!q2.empty() && (q1.empty() || (q2.top().first >= q1.top().first))) {
                auto [f, c] = q2.top();
                assert(c > 0); 
                q2.pop();
                if (2 * c % m == 0) {
                    ans += (2 * c / m) * f;
                    continue;
                } else {
                    ans += (2 * c / m) * f;
                    int res = c - (2 * c / m) * m;
                    k = m;
                    k -= 2 * res;
                    assert(k >= 0);
                    ans += f;
                }
            } else {
                assert(!q1.empty());
                auto [f, c] = q1.top();
                assert(c > 0); 
                q1.pop();
                if (c % m == 0) {
                    ans += (c / m) * f;
                    continue;
                } else {
                    ans += (c / m) * f;
                    int res = c - (c / m) * m;
                    k = m;
                    k -= res;
                    assert(k >= 0);
                    ans += f;
                }
            }
        } else {
            if (k >= 2 && (!q2.empty() && (q1.empty() || (q2.top().first >= q1.top().first)))) {
                auto [f, c] = q2.top();
                assert(c > 0); 
                q2.pop();
                int cnt = min(k / 2, c);
                k -= 2 * cnt;
                assert(k >= 0);
                assert(cnt <= c);
                if (cnt != c) q2.push({f, c - cnt}), assert(k <= 1);
            } else {
                if (q1.empty()) {
                    if (!q2.empty()) assert(k == 1);
                    k = 0;
                    continue;
                }
                auto [f, c] = q1.top();
                assert(c > 0);
                q1.pop();
                int cnt = min(k, c);
                k -= cnt;
                assert(k >= 0);
                assert(cnt <= c);
                if (cnt != c) q1.push({f, c - cnt}), assert(k == 0);
            }
        }
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}