#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5+10;

void solve()
{
    int n,k;
    cin>>n>>k;
    priority_queue<array<int, 3>>q;
    map<int,int>mp1,mp2;
    set<int>se;
    for(int i=1;i<=n;i++)
    {
        int c,w,f;
        cin>>c>>w>>f;
        if(w==1)
        {
            mp1[f]+=c;
        }
        else
        {
            mp2[f]+=c;
        }
        se.insert(f);
    }
    for(auto x:se)
    {
        q.push({x,mp2[x],mp1[x]});
    }
    int ans=0;
    int la=-1;
    while(q.size())
    {
        auto tt=q.top();
        int f=tt[0],c2=tt[1],c1=tt[2];
        q.pop();
        if(la==-1)
        {
            int x=c2/(k/2);
            int yu=c2%(k/2);
            ans+=x*f;
            int now=k-yu*2;
            if(yu)
            {
                ans+=f;
                if(c1>=now)
                    c1-=now;
                else
                {
                    now-=c1;
                    c1=0;
                    la=now;
                    continue;
                }
            }
            ans+=f*(c1/k);
            if(c1%k)
            {
                ans+=f;
                la=k-c1%k;
            }
        }
        else
        {
            if(2*c2+c1>=la)
            {
                int x=min(c2,la/2);
                c2-=x;
                la-=2*x;
                if(la)
                {
                    x=min(la,c1);
                    la-=x;
                    c1-=x;
                }
                if(la<=1) la=-1;
                if(c1||c2)
                    q.push({f,c2,c1});
            }
            else
            {
                la-=2*c2;
                la-=c1;
            }
        }
    }
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}