#include <bits/stdc++.h>		
using namespace std;
using ll = long long;
const int MAXN=1e6+7;
const ll mod=998244353LL;
int n,t;
ll m;
bool vis[MAXN];
ll ton[MAXN/3][3];
int tot=0,s[MAXN];
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		tot=0;
		for(int i=1;i<=n;i++)
		{
			ll v;
			int idk,sss;
			cin>>v>>idk>>sss;
			ton[sss][idk]+=v;
			if(!vis[sss]) vis[sss]=1,s[++tot]=sss;
		}
		sort(s+1,s+1+tot);
		ll ans=0LL;
		for(int i=1;i<=tot;i++)
		{
            // cerr<<s[i]<<" "<<ton[s[i]][1]<<" "<<ton[s[i]][2]<<"  asd"<<endl;
		}
		int now_id=tot;
        ll sumk=m,maxl=0;
		for(int i=tot;i>=1;i--)
		{
			ll sk=s[i];
            // cerr<<ans<<"  asd"<<endl;
            if(sumk==1)
            {
                bool kkk=0;
                for(int j=now_id;j>=1;j--)
                {
                    if(ton[s[j]][1]>0)
                    {
                        kkk=1;
                        now_id=j;
                        ton[s[j]][1]--;
                        maxl=max(maxl,(ll) s[j]);
                        break;
                    }
                }
                if(!kkk) now_id=0;
                ans+=maxl;
                sumk=m;maxl=0LL;
            }
			if(sumk>=ton[sk][2]*2LL)
            {
                sumk-=ton[sk][2]*2LL;
                if(ton[sk][2]>0) maxl=max(maxl,sk);
                ton[sk][2]=0LL;
            }
            else
            {
                if(sumk>0) maxl=max(maxl,sk);
                ton[sk][2]-=sumk/2;
                // if(i==tot-1) cerr<<ton[sk][2]<<" ads"<<endl;
                if(sumk%2)
                {
                    bool kkk=0;
                    for(int j=now_id;j>=1;j--)
                    {
                        if(ton[s[j]][1]>0)
                        {
                            kkk=1;
                            now_id=j;
                            ton[s[j]][1]--;
                            maxl=max(maxl,(ll) s[j]);
                            break;
                        }
                    }
                    if(!kkk) now_id=0;
                }
                // if(i==tot-1) cerr<<ton[sk][2]<<" asd"<<endl;
                ans+=maxl;

                ll numk=ton[sk][2]/(m/2LL);
                ans+=numk*sk;
                ton[sk][2]%=(m/2);
                
                sumk=m-ton[sk][2]*2;maxl=0LL;
                if(ton[sk][2]>0) maxl=max(maxl,sk);
                ton[sk][2]=0;
            }
            
            if(sumk>=ton[sk][1])
            {
                sumk-=ton[sk][1];
                if(ton[sk][1]>0) maxl=max(maxl,sk);
                ton[sk][1]=0LL;
            }
            else
            {
                if(sumk>0) maxl=max(maxl,sk);
                ton[sk][1]-=sumk;

                ans+=maxl;

                ll numk=ton[sk][1]/m;
                ans+=sk*numk;
                ton[sk][1]%=m;

                sumk=m-ton[sk][1];maxl=0;
                
                if(ton[sk][1]>0) maxl=max(maxl,sk);
            }
			
		}
        if(sumk!=m) ans+=maxl;
		cout<<ans<<'\n';
		for(int i=1;i<=tot;i++)
		{
			ton[s[i]][1]=ton[s[i]][2]=0LL;
			vis[s[i]]=0;
		}
	}
	return 0;
}
/*
aabbaA
		
*/