#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int n, m, k;
int res = 0;
int in[N];
int a[N];
bool cmp(int a, int b)
{
    return a > b;
}
map<int, int> mp2;
map<int, int> mp;
void solve()
{
    mp2.clear();
    mp.clear();
    cin >> n >> k;
    int cnt = 0;
    int u = 0;
    for (int i = 1; i <= n; i++)
    {
        int c, w, h;
        cin >> c >> w >> h;
        if (!mp[h])
            a[++cnt] = h;
        mp[h] = 1;
        if (w == 1)
        {
            mp2[h] += c / 2;
            if (c % 2 != 0)
            {
                if(u==0) mp2[h]++;
                u ^= 1;
            }
        }
        else
        {
            mp2[h] += c;
        }
    }
    sort(a + 1, a + 1 + cnt, cmp);
    int res = 0;
    int t = 0;
    int now = a[1];
    k /= 2;
    for (int i = 1; i <= cnt; i++)
    {
        // cout << a[i] << " " << mp2[a[i]] << endl;
        int o = min(k - t, mp2[a[i]]);
        mp2[a[i]] -= o;
        t += o;
        if (t == k)
        {
            // cout << "   " << res << " " << now << endl;
            t = 0;
            res += now;
        }
        res += (mp2[a[i]] / k) * a[i];
        mp2[a[i]] %= k;
        if (mp2[a[i]])
        {
            now = a[i];
            t += mp2[a[i]];
        }
        // cout << " " << res << " " << t << endl;
    }
    if (t)
    {
        res += now;
    }
    cout << res << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}