#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n;
long long K, ans;
vector<pii> A;

void solve() {
    scanf("%d%lld", &n, &K);

    A.clear();
    for (int i = 1; i <= n; i++) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        A.push_back(pii(-z, x * y));
    }
    sort(A.begin(), A.end());

    ans = 0;
    long long now = -A[0].first, sm = 0;
    for (pii p : A) {
        sm += p.second;
        if (sm > K) {
            ans += now;
            now = -p.first;
            sm -= K;
            long long t = (sm - 1) / K;
            ans += now * t;
            sm -= t * K;
        }
    }
    ans += now;

    printf("%lld\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}