#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define __count __builtin_popcountll
#define yes cout<<"Yes\n";
#define no cout<<"No\n";
using namespace std;

void solve() {
    ll n, k;
    cin >> n >> k;
    std::vector<ll> c(n), w(n), f(n), p(n);
    std::iota(p.begin(), p.end(), 0);
    for (int i = 0; i < n; ++i) {
        cin >> c[i] >> w[i] >> f[i];
    }

    sort(p.begin(), p.end(), [&](ll i, ll j) {
        return f[i] > f[j];
    });

    ll ans = 0, old = f[p[0]], sum = 0;
    for (auto i: p) {
        sum += c[i] * w[i];
        if (sum > k) {
            sum -= k;
            ans += old;
            old = f[i];

            ll t = (sum - 1) / k;
            ans += t * old;
            sum -= t * k;
        }
    }
    ans += old;
    cout << ans << endl;

}

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

    ll t = 1;
    cin >> t;
    while (t--)
        solve();
}