#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define x first
#define y second
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
pii a[N];
int cmp(pii a, pii b)
{
    // if (a.first == b.first) return a.second > b.second;
    // return a.first < b.first;
    return a.second > b.second;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int c, w, f;
        cin >> c >> w >> f;
        ans += c * w / k * f;
        a[i] = {c * w % k, f};
    }
    sort(a + 1, a + n + 1, cmp);
    int mx = a[1].second, sum = a[1].first;
    for (int i = 2; i <= n; i++)
    {
        // cout << a[i].first << ' ' << a[i].second << endl;
        if (sum + a[i].first > k)
        {
            ans += mx;
            mx = a[i].second;
            sum = a[i].first;
            a[i].first -= (k - sum);
        }
        else sum += a[i].first;
    }
    ans += mx;
    cout << ans << endl;
}
signed main()
{
    // freopen("D:\\3022244240\\vscode\\txt\\in.txt", "r", stdin);
    // freopen("D:\\3022244240\\vscode\\txt\\out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}