#include<bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a;
    vector<array<ll, 3>> b;
    for (int i = 1; i <= n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        c = c * w;
        b.push_back({f, c, w});
    }
    sort(b.begin(), b.end(), greater<>());
    ll res = 0, now = 0, re = 0;
    ll ans = 0;
    for (auto &[f, c, w]: b) {
        if (w == 1) {
            ll mi = min(c, re);
            c -= mi;
            re -= mi;
            if (c == 0) continue;
        }
        if (c >= res) {
            re += res % w;
            c -= res / w * w;
            ans += now + c / k * f;
            res = k - c % k;
            if (res == k) res = 0;
            if (c % k) {
                now = f;
            } else now = 0;
        } else {
            res -= c;
            now = max(now, f);
        }
//        cerr << now << " " << res << " " << ans << "\n";

    }
    ans += now;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _;
    for (; _; _--)solve();
    return 0;
}