#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";

using namespace std;
const int Mod = 998244353;
using ll = long long;
ll C, W, F, a[3][100010], Fmax, t1, t2, n, k, ans, sum, maxn;

void solve()
{
    cin >> n >> k;
    Fmax = 0;
    ans = 0;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; i++)
    {
        cin >> C >> W >> F;
        a[W][F] += C * W;
        ans += (a[W][F] / k) * F;
        a[W][F] %= k;
        Fmax = max(Fmax, F);
    }
    t1 = t2 = Fmax;
    while (t1 || t2)
    {
        while (t1 > 0 && !a[1][t1])
            t1--;
        while (t2 > 0 && !a[2][t2])
            t2--;
        if (sum == k || sum == k - 1 && t1 == 0 || t1 == 0 && t2 == 0)
        {
            ans += maxn;
            sum = 0;
        }
        if (sum == 0)
            maxn = max(t1, t2);
        if (t2 >= t1 && k - sum != 1)
        {
            if (k - sum > a[2][t2])
            {
                sum += a[2][t2];
                a[2][t2] = 0;
            }
            else
            {
                a[2][t2] -= (k - sum) / 2 * 2;
                sum += (k - sum) / 2 * 2;
            }
        }
        else
        {
            if (k - sum > a[1][t1])
            {
                sum += a[1][t1];
                a[1][t1] = 0;
            }
            else
            {
                a[1][t1] -= (k - sum);
                sum += (k - sum);
            }
        }
    }
    cout << ans << '\n';
}
int main()
{
    IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
    clock_t start_time = clock();
#endif
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
#ifndef ONLINE_JUDGE
    cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
    return 0;
}