#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

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

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

	return 0;

}