#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::vector<int> odd;
    for (int i = 0; i < n; i++) {
        std::cin >> c[i] >> w[i] >> f[i];

        if (w[i] == 1) {
            odd.emplace_back(i);
        }
    }

    std::sort(odd.begin(), odd.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) {
        while (!odd.empty() && !c[odd.back()]) {
            odd.pop_back();
        }

        assert(lst >= 0);
        if (lst >= 1LL * c[i] * w[i]) {
            lst -= 1LL * c[i] * w[i];
            c[i] = 0;
        } else {
            i64 times = lst / w[i];
            c[i] -= times;
            lst -= times * w[i];
            if (lst == 1) {
                if (!odd.empty()) {
                    c[odd.back()]--;
                }
            }
            lst = 0;
        }
        if (!c[i]) {
            continue;
        }
        i64 times = (1LL * c[i] * w[i] + k - 1) / k;
        ans += f[i] * times;
        lst = k * times - 1LL * c[i] * w[i];
        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;
}