#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

struct Group
{
	ll c,w,f;
	auto operator<=>(const Group& o) const { return f <=> o.f; }
};

void solve()
{
	int n; ll K; cin>>n>>K;
	vector<Group> a[2];
	forn(i,0,n)
	{
		ll c,w,f; cin>>c>>w>>f;
		a[w - 1].pb({c, w, f});
	}
	forn(i,0,2) sort(all(a[i]));
	ll ans = 0;
	while (!a[0].empty() || !a[1].empty())
	{
		ll rem = K;
		while (rem > 0)
		{
			int id = 0;
			if (a[0].empty())
			{
				if (rem < 2) break;
				id = 1;
			}
			else if (a[1].empty()) id = 0;
			else
			{
				id = (a[0].back() > a[1].back() ? 0 : 1);
				if (rem < 2) id = 0;
			}
			Group cur = a[id].back();
			if (cur.c > rem)
			{
				ll inc = rem / cur.w;
				ans += inc;
				rem -= inc * cur.w;
				a[id].back().c -= inc;
			}
			if (cur.c == 0)
				a[id].pop_back();
		}
	}
	cout << ans << '\n';
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int t; cin>>t;
	fore(i,1,t) solve();

	return 0;
}

answer.code:56:14: error: declaration of ‘operator<=’ as non-function
   56 |         auto operator<=>(const Group& o) const { return f <=> o.f; }
      |              ^~~~~~~~
answer.code:56:22: error: expected ‘;’ at end of member declaration
   56 |         auto operator<=>(const Group& o) const { return f <=> o.f; }
      |                      ^~
      |                        ;
answer.code:56:24: error: expected unqualified-id before ‘>’ token
   56 |         auto operator<=>(const Group& o) const { return f <=> o.f; }
      |                        ^
answer.code: In function ‘void solve()’:
answer.code:84:51: error: no match for ‘operator>’ (operand types are ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} and ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’})
   84 |                                 id = (a[0].back() > a[1].back() ? 0 : 1);
      |                                       ~~~~~~~~~~~ ^ ~~~~~~~~~~~
      |                                                |             |
      |                                                |             __gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type {aka Group}
      |                                                __gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type {aka Group}
In file included from /usr/include/c++/13/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:181,
                 from answer.code:1:
/usr/include/c++/13/bits/regex.h:1176:5: note: candidate: ‘template<class _BiIter> bool std::__cxx11::operator>(const sub_match<_BiIter>&, const sub_match<_BiIter>&)’
 1176 |     operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1176:5: note:   template argument deduction/substitution failed:
answer.code:84:63: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   84 |                                 id = (a[0].back() > a[1].back() ? 0 : 1);
      |                                                               ^
/usr/include/c++/13/bits/regex.h:1236:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)’
 1236 |     operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1236:5: note:   template argument deduction/substitution failed:
answer.code:84:63: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} is not derived from ‘std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>’
   84 |                                 id = (a[0].back() > a[1].back() ? 0 : 1);
      |                                                               ^
/usr/include/c++/13/bits/regex.h:1329:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’
 1329 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1329:5: note:   template argument deduction/substitution failed:
answer.code:84:63: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   84 |                                 id = (a[0].back() > a[1].back() ? 0 : 1);
      |                                                               ^
/usr/include/c++/13/bits/regex.h:1403:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)’
 1403 |     operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1403:5: note:   template argument deduction/substitution failed:
answer.code:84:63: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   84 |                                 id = (a[0].back() > a[1].back() ? 0 : 1);
      |                                                               ^
/usr/include/c++/13/bits/regex.h:1497:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator>(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’
 1497 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1497:5: note:   template argument deduction/substitution failed:
answer.code:84:63: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<Group>, Group>::value_type’ {aka ‘Group’} is not derived from ‘const std::__cxx11::sub_...