#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;

int f[N][2];
int sumef[N];

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> idx0, idx1;
    int alle = 0;
    vector <int> c(n+1),w(n+1),ff(n+1);
    for (int i = 1; i <= n; ++i)
    {
      //  int c, w, ff;
        cin >> c[i] >> w[i] >> ff[i];

        if (w[i] % 2 == 1)
        {

            if (!sumef[ff[i]])
                idx1.emplace_back(ff[i]);
            sumef[ff[i]] += c[i];
            alle++;
        }
        else
        {
            if (!f[ff[i]][0])
                idx0.emplace_back(ff[i]);
            f[ff[i]][0] += c[i];
        }
    }

        k /= 2;

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

        int resv = 0;
        int resc = 0;

        sort(idx1.begin(), idx1.end());
        reverse(idx1.begin(), idx1.end());

        for (auto e : idx1)
        {
            // while (e >= 1 && sumef[e] == 0)
            //     e--;
            // if (e < 1)
            //     break;
            //  cout << e << " ";

            if (resc == 0)
            {
                if (sumef[e] / 2 >= 1)
                {
                    if (!f[e][0])
                        idx0.emplace_back(e);
                    f[e][0] += sumef[e] / 2;
                }

                sumef[e] %= 2;
                if (sumef[e])
                {
                    resc = 1;
                    resv = e;
                    sumef[e] = 0;
                }
            }
            else
            {
                sumef[e]--;
                if (!f[resv][0])
                    idx0.emplace_back(resv);
                f[resv][0]++;
                resc = 0;
                if (sumef[e] / 2 >= 1)
                {
                    if (!f[e][0])
                        idx0.emplace_back(e);
                    f[e][0] += sumef[e] / 2;
                }

                sumef[e] %= 2;
                if (sumef[e])
                {
                    resc = 1;
                    resv = e;
                    sumef[e] = 0;
                }
            }
        }
        //  cout << endl;
        int ans = 0;
        if (resc)
        {
             if (!f[resv][0])
                    idx0.emplace_back(resv);
            f[resv][0]++;
        }

        // while (o >= 1 && f[o][0] == 0)
        //     o--;
        sort(idx0.begin(), idx0.end());
        reverse(idx0.begin(), idx0.end());

        resv = 0;
        resc = 0;

        for (auto o : idx0)
        {
            // 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
*/