#include <bits/stdc++.h>

#define ll long long

void solve(){
    ll n, k;
    std::cin >> n >> k;

    std::vector<std::pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++){
        ll c, w, f;
        std::cin >> c >> w >> f;
        a[i] = {f, c * w};
    }
    std::sort(a.begin(), a.end(), std::greater<>());
    ll ans = 0;
    ll now = a[0].first, siz = 0;
    for (auto [x, y] : a){
        if (siz + y <= k){
            siz += y;
        }else{
            ans += now;
            now = x;
            ll d = k - siz;
            y -= d;
            ll t = (y - 1) / k;
            ans += t * x;
            siz = (y - 1) % k + 1;
        }
    }
    ans += now;
    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;
}