#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define db double
#define endl '\n'
#define lowbit(x) x&-x
#define intz(x,a) memset(x,a,sizeof(x));
const int N=1e5+5;
struct node{int c,w,f;}a[N];
int b[N],tot,cnt[N][3];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T;cin>>T;
	while(T--){tot=0;intz(cnt,0);
		int n,k,ans=0;cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i].c>>a[i].w>>a[i].f,b[++tot]=a[i].f;tot=unique(b+1,b+1+tot)-b-1;sort(b+1,b+1+tot);
		for(int i=1;i<=n;i++){a[i].f=lower_bound(b+1,b+1+tot,a[i].f)-b;cnt[a[i].f][a[i].w]+=a[i].c;;}
		for(int i=tot;i;i--){
			if(!cnt[i][2]&&!cnt[i][1])continue;
			if(cnt[i][2]*2>k)ans+=b[i]*(cnt[i][2]/(k/2)),cnt[i][2]%=k/2,++i;
			else if(!cnt[i][2]&&cnt[i][1]>=k)ans+=b[i]*(cnt[i][1]/k),cnt[i][1]%=k,++i;
			else if(cnt[i][2]*2<=k){
				if(cnt[i][2]*2+cnt[i][1]<=k){ans+=b[i];int kk=k-cnt[i][2]*2-cnt[i][1],l=i-1;
					while(l&&kk){int t=min(kk/2*2,cnt[l][2]*2);kk-=t,cnt[l][2]-=t/2;if(kk){int t=min(kk,cnt[l][1]);kk-=t,cnt[l][1]-=t;}--l;}
				}else ans+=b[i],cnt[i][1]-=k-cnt[i][2]*2,cnt[i][2]=0,++i;
			}
		}cout<<ans<<endl;
	}
	return 0;
}
/*
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

23
*/