#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5;

	int n;
	LL k;
	LL a[N + 3][2];				//floor i; even, odd
	int m, b[N + 3];
	
void next(int &f){
	int i = lower_bound(b + 1, b + m + 1, f) - b - 1;
	if(i == m)
		f = 0;
	else 
		f = b[i + 1];
}

void sol(){
	scanf("%d%lld", &n, &k);
	
	memset(a, 0, sizeof a);
	m = 0;
	for(int i = 1, c, w, f; i <= n; i++){
		scanf("%d%d%d", &c, &w, &f);
		a[f][w & 1] += c;
		b[++m] = f;
	}
	
	sort(b + 1, b + m + 1, greater<int>());
	m = unique(b + 1, b + m + 1) - b - 1;
		
	int oddpos = 1;
	LL ans = 0;
	for(int i = 1; i <= m;){
		while(i <= m && a[b[i]][0] == 0 && a[b[i]][1] == 0)
			i++;
		if(i == m + 1)
			break;
		
		LL tmp = 0;
		int cost = b[i];
		while(i <= m && (tmp + 2 * a[b[i]][0] + a[b[i]][1] <= k)){
			tmp += 2 * a[b[i]][0] + a[b[i]][1];
			i++;
		}
		if(i == m + 1){
			ans += cost;
			break;
		}
		if(tmp == k){
			ans += cost;
			continue;
		}
		
		if(tmp + 2 * a[b[i]][0] > k){
			a[b[i]][0] -= (k - tmp) / 2;
			if(tmp & 1){
				if(a[b[i]][1] > 0)
					a[b[i]][1]--;
				else {
					while(oddpos <= i || (oddpos <= m && a[oddpos][0] == 0))
						oddpos++;
					if(oddpos <= m){
						a[oddpos][1]--;
					}
				}
			}
			ans += cost;
			
			if(2 * a[b[i]][0] >= k){
				LL div = 2 * a[b[i]][0] / k;
				ans += b[i] * div;
				a[b[i]][0] -= div * k / 2;
			}
			
			continue;
		}
		
		tmp += 2 * a[b[i]][1];
		a[b[i]][1] -= k - tmp;
		ans += cost;
		
		if(a[b[i]][1] >= k){
			LL div = a[b[i]][1] / k;
			ans += b[i] * div;
			a[b[i]][1] -= div * k;
		}
		
	}
	
	printf("%lld\n", ans);
	
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--)
		sol();

	return 0;

}