#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 1e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
LL n , m;
LL a[N];
vector<vector<LL>>cnt_f(N , vector<LL>(2));
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0 ,cnt_f[i][0] = cnt_f[i][1] = 0;
	}
}
void solve() 
{
	cin >> n >> m;	
	set<LL>num;
	set<int>st[2];
	for(int i = 0 ; i < n ; i ++){
		LL x , y , z;
		cin >> x >> y >> z;
		num.insert(z);
		cnt_f[z][y - 1] += x;
		st[y - 1].insert(z);
	}
	vector<LL>f;
	for(auto it : num){
		f.pb(it);
	}
	auto cmp = [&](int x , int y){
		return x > y;
	};
	sort(f.begin() , f.end() , cmp);
	LL res = 0;
	int len = f.size();
	for(int i = 0 ; i < len ; ){
		LL eve = m;
		LL t = f[i];
		while(i < len && eve >= cnt_f[f[i]][0] + cnt_f[f[i]][1] * 2){
			eve -= cnt_f[f[i]][0] + cnt_f[f[i]][1] * 2;
			st[0].erase(f[i]);
			st[1].erase(f[i]);
			cnt_f[f[i]][0] = 0;
			cnt_f[f[i]][1] = 0;
			i++;
		}
		if(i >= len){
			res += t;
			break;
		}
		if(eve >= cnt_f[f[i]][1] * 2){
			eve -= cnt_f[f[i]][1] * 2;
			cnt_f[f[i]][1] = 0;
			st[1].erase(f[i]);
		}
		else{
			cnt_f[f[i]][1] -= eve / 2;
			eve = eve % 2 == 0 ? 0 : 1;
		}
		if(eve >= cnt_f[f[i]][0]){
			eve -= cnt_f[f[i]][0];
			cnt_f[f[i]][0] = 0;
			st[0].erase(f[i]);			
		}
		else{
			cnt_f[f[i]][0] -= eve;
			eve = 0;	
		}
		if(eve > 0){
			auto it = st[0].lower_bound(f[i]);
			if(it != st[0].begin()){
				it--;
				int x = *it;
				cnt_f[x][0]--;
				if(cnt_f[x][0] == 0){
					st[0].erase(x);
				}
			}
		}
		res += t;
	}
	cout << res << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}