#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

void solve()
{
	int n;
	LL k;
	cin >> n >> k;
	map<int, LL> mp[2];
	while (n--)
	{
		int c, w, f;
		cin >> c >> w >> f;
		mp[w - 1][f] += c;
	}
	LL ans = 0;
	while (!mp[0].empty() || !mp[1].empty())
	{
		int x = !mp[1].empty() && (mp[0].empty() || prev(mp[1].end())->F > prev(mp[0].end())->F) ? 1 : 0;
		int f = prev(mp[x].end())->F;
		LL m = k / (x + 1);
		if (m <= prev(mp[x].end())->S)
		{
			ans += (prev(mp[x].end())->S / m) * f;
			prev(mp[x].end())->S %= m;
			if (prev(mp[x].end())->S == 0)
				mp[x].erase(prev(mp[x].end()));
			continue;
		}
		LL cur = 0;
		f = -1;
		while (!mp[0].empty() || !mp[1].empty())
		{
			x = !mp[1].empty() && (mp[0].empty() || prev(mp[1].end())->F > prev(mp[0].end())->F) ? 1 : 0;
			if (f == -1)
				f = prev(mp[x].end())->F;
			m = (k - cur) / (x + 1);
			if (m == 0)
				break;
			if (m < prev(mp[x].end())->S)
			{
				cur += m * (x + 1);
				prev(mp[x].end())->S -= m;
			}
			else
			{
				cur += prev(mp[x].end())->S * (x + 1);
				mp[x].erase(prev(mp[x].end()));
			}
		}
		if (cur == k - 1 && !mp[0].empty())
		{
			f = prev(mp[x].end())->F;
			prev(mp[x].end())->S--;
			if (prev(mp[x].end())->S == 0)
				mp[x].erase(prev(mp[x].end()));
			cur++;
		}
		ans += f;
	}
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);	
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}