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

#define int long long
#define endl '\n'
typedef unsigned long long ull;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> f(N, vector<int>(3, 0));
    vector<int> sumef(N, 0);
    // int alle=0;
    for (int i = 1; i <= n; ++i)
    {
        int c, w, ff;
        cin >> c >> w >> ff;
        f[ff][w % 2] += c;
        if (w % 2 == 1)
        {
            sumef[ff] += c;
            //  alle++;
        }
    }
   // cout << "test1 \n";
    k/=2;

    int o = N - 1, e = N - 1;

    int resv = 0;
    int resc = 0;

    while (e >= 1)
    {
        while (e >= 1 && sumef[e] == 0)
            e--;
        if (e < 1)
            break;

        if (resc == 0)
        {
            f[e][0] += sumef[e] / 2;
            sumef[e] %= 2;
            if (sumef[e])
            {
                resc = 1;
                resv = e;
                sumef[e]=0;
            }
        }
        else
        {
            sumef[e]--;
            f[resv][0]++;
            resc = 0;
            f[e][0] += sumef[e] / 2;
            sumef[e] %= 2;
            if (sumef[e])
            {
                resc = 1;
                resv = e;
                sumef[e]=0;
            }
        }
    }
    int ans = 0;
    if (resc)
    {
        ans += resv;
    }

    while (o >= 1 && f[o][0] == 0)
        o--;

    resv = 0;
    resc = 0;

    while (o >= 1)
    {
        while (o >= 1 && f[o][0] == 0)
        {
            o--;
        }
        if (o < 1)
            break;
      //  cerr << o << " " << f[o][0] << endl;
        if (resc == 0)
        {
            ans += f[o][0]/k * o;
            f[o][0] %= k;
            resc = f[o][0];
            resv = o;
            f[o][0]=0;
        }
        else
        {
            if (resc + f[o][0] <= k)
            {
                resc += f[o][0];
                f[o][0]=0;
                continue;
            }
            f[o][0] -= (k - resc);
            ans += resv;
            resv = -1;
            resc = 0;

            ans += f[o][0]/k  * o;
            f[o][0] %= k;
            resc = f[o][0];
            resv = o;
            f[o][0]=0;
        }
    }

    if (resc)
    {
        ans += resv;
    }

    cout << ans << endl;
}

signed main()
{
    // cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve();
    }
    return 0;
}
/*
2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345


1
4 6
1 1 8
7 2 5
1 1 7
3 2 6
*/