#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;
    for (int i = 1; i <= n; ++i)
    {
        int c, w, ff;
        cin >> c >> w >> ff;

        if (w % 2 == 1)
        {

            if (!sumef[ff])
                idx1.emplace_back(ff);
            sumef[ff] += c;
            //  alle++;
        }
        else
        {
            if (!f[ff][0])
                idx0.emplace_back(ff);
            f[ff][0] += c;
        }
    }
    // cout << "test1 \n";
    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)
    {
        ans += resv;
    }

    // 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
*/