#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#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;
    for (int i = 0; i <= n; i++) 
    {
        e[i] = e2[i] = {0, 0, 0};
        nex[i] = 0;
    }

    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 <= n; 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;
    }
    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("C:\\Users\\86159\\Desktop\\duipai\\output\\in.txt","r",stdin); //输入重定向，输入数据将从D盘根目录下的in.txt文件中读取 
    // freopen("C:\\Users\\86159\\Desktop\\duipai\\output\\out1.txt","w",stdout); //输出重定向，输出数据将保存在D盘根目录下的out.txt文件中

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}