#include <bits/stdc++.h>

using i64 = long long;

// 11:01

void solve() {
    int n;
    i64 k;
    std::cin >> n >> k;

    std::vector<int> c(n), w(n), f(n);
    std::array<std::vector<int>, 2> v;
    for (int i = 0; i < n; i++) {
        std::cin >> c[i] >> w[i] >> f[i];

        v[w[i] % 2].emplace_back(i);
    }

    for (int i = 0; i < 2; i++) {
        std::sort(v[i].begin(), v[i].end(), [&](int x, int y) {
            return f[x] < f[y];
        });
    }

    std::vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(), [&](const int &i, const int &j) {
        return f[i] > f[j];
    });

    i64 ans = 0, lst = 0;
    for (const auto &i : p) {
        for (int j = 0; j < 2; j++) {
            while (!v[j].empty() && !c[v[j].back()]) {
                v[j].pop_back();
            }
        }
        if (lst >= 1LL * c[i] * w[i]) {
            lst -= 1LL * c[i] * w[i];
            c[i] = 0;
            continue;
        } else { // lst < 
            i64 cost = std::min(lst, 1LL * c[i] * w[i]);
            i64 t = cost / w[i];
            c[i] -= t;
            lst -= cost;
            if (lst == 1) {
                if (!v[1].empty()) {
                    int id = v[1].back();
                    c[id]--;
                }
            }
            lst = 0;
        }
        if (!c[i]) {
            continue;
        }
        if (k >= 1LL * c[i] * w[i]) {
            ans += f[i];
            lst = k - 1LL * c[i] * w[i];
        } else {
            i64 times = (1LL * c[i] * w[i] + k - 1) / k;
            ans += f[i] * times;
            lst = 1LL * c[i] * w[i] % k;
        }
        c[i] = 0;
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}