#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int mp[N], ump[N];

void solve()
{
    int n, k; cin >> n >> k;
    vector<int> c(n + 1), w(n + 1), f(n + 1), tt;
    int maxx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> c[i] >> w[i] >> f[i];
        tt.push_back(f[i]);
    }
    sort(tt.begin(), tt.end());
    tt.erase(unique(tt.begin(), tt.end()), tt.end());
    for (int i = 0; i < tt.size(); i ++ )
    {
        mp[tt[i]] = i + 1;
        ump[i + 1] = tt[i];
    }
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = mp[f[i]];
        maxx = max(maxx, f[i]);
    }
    vector<vector<int>> cnt(maxx + 1, vector<int>(3));
    for (int i = 1; i <= n; i ++ ) cnt[f[i]][w[i]] += c[i];
    int ans = 0, yu = 0;
    bool flag = false;
    for (int i = maxx; i >= 1; i -- )
    {
        if (flag && cnt[i][1] != 0)
        {
            flag = false;
            cnt[i][1] -- ;
        }
        if (yu != 0)
        {
            int t1 = yu / 2; // 放多少重量为2的
            if (cnt[i][2] >= t1)
            {
                cnt[i][2] -= t1;
                yu %= 2;
            }
            else
            {
                yu -= cnt[i][2] * 2;
                cnt[i][2] = 0;
            }
            if (yu != 0)
            {
                if (cnt[i][1] >= yu)
                {
                    cnt[i][1] -= yu;
                    yu = 0;
                }
                else
                {
                    yu -= cnt[i][1];
                    cnt[i][1] = 0;
                }
            }
            if (yu == 1)
            {
                yu = 0;
                flag = true;
            }
        }
        if (cnt[i][2] != 0) // 本楼层还有重量为2的
        {
            int tmp2 = k / 2; // 一趟能运多少重量为2

            // 全是本楼层重量为2的
            int c1 = cnt[i][2] / tmp2;
            ans += c1 * ump[i];
            cnt[i][2] %= tmp2;

            if (cnt[i][2] != 0)
            {
                int wei = k - cnt[i][2] * 2; // 还能装多少重量
                cnt[i][2] = 0;
                if (wei != 0)
                {
                    if (cnt[i][1] >= wei) // 剩下的部分全装本楼层重量为1的
                    {
                        cnt[i][1] -= wei;
                        ans += ump[i];
                    }
                    else
                    {
                        wei -= cnt[i][1];
                        cnt[i][1] = 0;
                        yu += wei;
                        ans += ump[i];
                        if (yu == 1)
                        {
                            yu = 0;
                            flag = true;
                        }
                    }
                }
            }
        }
        if (cnt[i][1] != 0)
        {
            int t = cnt[i][1] / k;
            ans += t * ump[i];
            cnt[i][1] %= k;
            if (cnt[i][1] != 0)
            {
                ans += ump[i];
                yu += k - cnt[i][1];
                cnt[i][1] = 0;
            }
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}