#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
using i128 = __int128;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const i64 inf = 2e18;
//-------------------------------------------
struct node
{
    int c, w, f;
};

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<node> a(n);
    vector<pii> b;
    map<int, int> cnt;
    for (auto &[c, w, f] : a)
    {
        cin >> c >> w >> f;
        if (w == 2)
            cnt[f] += c;
        if (w == 1)
            b.push_back({f, c});
    }
    sort(b.begin(), b.end());
    int st = 0;

    for (int i = b.size() - 1; i >= 0; i--)
    {
        b[i].y -= st;
        st = 0;
        if (b[i].y % 2 == 1)
        {
            cnt[b[i].x]++;
            st = 1;
        }
        cnt[b[i].x] += b[i].y / 2;
    }

    auto r = cnt.end();
    r--;
    k /= 2;
    int ans = 0, w = 0;
    while (1)
    {
        auto [f, c] = *r;
        cerr << f << " " << c << endl;
        int ct = max(0LL, (c - w + k - 1) / k);
        ans += ct * f;
        w = ct * k - (c - w);
        if (r != cnt.begin())
            r--;
        else
            break;
    }

    cout << ans << endl;

    // 1.优先送楼层最高的，把楼层近可能高的绑到一起送
    // 2.重量要正好填满，优先消耗重量为1的
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
        solve();
    return 0;
}