#include<bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    int T; cin >> T;
    while(T--)
    {
        int n;
        long long k, ans = 0;
        cin >> n >> k;

        vector<array<int, 2>> a(n);

        for(auto &[p, q] : a)
        {
            int x, y; cin >> x >> y >> p;
            q = x * y;
        }
        sort(a.begin(), a.end(), greater());

        long long now = a[0][0], sm = 0;
        for (auto [p, q] : a)
        {
            sm += q;
            if(sm > k)
            {
                ans += now; now = p; sm -= k;
                long long t = (sm - 1) / k;
                ans += now * t;
                sm -= t * k;
            }
        }
        ans += now;

        cout << ans << "\n";
    }
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:16:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   16 |         for(auto &[p, q] : a)
      |                   ^
answer.code:21:41: error: missing template arguments before ‘(’ token
   21 |         sort(a.begin(), a.end(), greater());
      |                                         ^
answer.code:24:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   24 |         for (auto [p, q] : a)
      |                   ^