#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define x first
#define y second
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
int nex[N];
struct node
{
    int c, w, f;
}e[N], e2[N];
int cmp(node a, node b)
{
    return a.f > b.f;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = 0, lst = n + 1, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int c, w, f;
        cin >> c >> w >> f;
        e[i] = {c, w, f};
        ans += c * w / k * f;
        if (c * w % k > 0) e2[++cnt] = {w, c * w % k, f};
    }
    for (int i = 1; i <= cnt; i++) e[i] = e2[i];
    sort(e + 1, e + cnt + 1, cmp);
    for (int i = cnt; i >= 1; i--)
    {
        auto [c, w, f] = e[i];
        nex[i] = lst;
        if (c & 1) lst = i;
        // else nex[i] = lst;
    }
    // for (int i = 1; i <= cnt; i++) cout << nex[i] << ' ';
    // cout << endl;
    int mx = e[1].f, sum = e[1].w;
    for (int i = 2; i <= cnt; i++)
    {
        if (e[i].w == 0) continue;
        if (sum + e[i].w > k)
        {
            ans += mx;
            if (e[i].c & 1) e[i].w -= (k - sum);
            else 
            {
                if ((k - sum) & 1) 
                {
                    e[i].w -= (k - sum - 1), e[nex[i]].w -= 1;
                }
                else e[i].w -= (k - sum);
            }
            mx = e[i].f;
            sum = e[i].w;
        }
        else sum += e[i].w;
    }
    ans += mx;
    cout << ans << endl;
}
signed main()
{
    // freopen("D:\\3022244240\\vscode\\txt\\in.txt", "r", stdin);
    // freopen("D:\\3022244240\\vscode\\txt\\out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}

/*
1
6 4
1 2 8
1 1 7
1 2 6
1 1 5
1 2 5
1 1 4
1 1 3
1 1 2 

1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
*/