#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
#define Genshin_Impact return
#define start 0
const int mod = 998244353;
priority_queue<pii> q[3];
mt19937_64 rng{chrono::steady_clock::now().time_since_epoch().count()};
void solve()
{
    int n, m;
    cin >> n >> m;
    //n = 5, m = (rng() % 10 + 1) * 2;
    //cout << n << ' ' << m << '\n';
    for (int i = 1; i <= n; i++)
    {
        int ns, w, lc;
        cin >> ns >> w >> lc;
        // ns = rng() % 10 + 1;
        // w = rng() % 2 + 1;
        // lc = rng() % 10 + 1;
        // cout << ns << ' ' << w << ' ' << lc << '\n';
        if (w == 1)
            q[1].push({lc, ns});
        else
            q[2].push({lc, ns});
    }
    int ans = 0;
    int sum = 0;
    int mxlc = 0;
    while (q[1].size() || q[2].size())
    {
        int mx1 = -1, mx2 = -1;
        if (q[1].size())
            mx1 = q[1].top().first;
        if (q[2].size())
            mx2 = q[2].top().first;
        if (sum == m - 1)
        {
            if (q[1].empty())
            {
                sum = 0;
                ans += mxlc;
                mxlc = 0;
                continue;
            }
            auto [lc, num] = q[1].top();
            q[1].pop();
            int nd = 1;
            sum++;
            mxlc = max(mxlc, lc);
            if (num != 1)
                q[1].push({lc, num - 1});
        }
        else if (mx1 > mx2)
        {
            auto [lc, num] = q[1].top();
            q[1].pop();
            int nd = min(num, m - sum);
            sum += nd;
            mxlc = max(mxlc, lc);

            if (nd != num)
            {
                ans += mxlc;
                num -= nd;
                int p = num / m;
                ans += lc * p;
                num -= p * m;
                sum = 0;
                mxlc = 0;
                if (num != 0)
                    q[1].push({lc, num});
            }
        }
        else
        {
            auto [lc, num] = q[2].top();
            q[2].pop();
            int nd = min(num, (m - sum) / 2);
            sum += nd * 2;
            mxlc = max(mxlc, lc);
            if (nd != num)
            {
                ans += mxlc;
                num -= nd;
                int p = num / (m / 2);
                ans += p * lc;
                num -= p * (m / 2);
                sum = 0;
                mxlc = 0;
                if (num != 0)
                    q[2].push({lc, num});
            }
        }
        if (sum == 0)
            continue;
        if (sum == m || (sum == m - 1 && q[1].empty()) || (q[1].empty() && q[2].empty()))
        {
            sum = 0;
            ans += mxlc;
            mxlc = 0;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    Genshin_Impact start;
}