#include <bits/stdc++.h>
using namespace std;
#define el      	'\n'
#define ft 			first
#define sd 			second
#define mp(x,y)  	make_pair((x),(y))
#define pb(x)    	push_back((x))
#define all(v)  	((v).begin()),((v).end())
#define sz(x)  		((int) (x).size())
#define clr(a,b)	memset(a,b,sizeof(a))
typedef long long ll;
void Yahia74() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}
const int N = 1e3 + 74, OO = 0x3f3f3f3f, MOD = (int) 1e9 + 7;

vector<pair<int, int> > adj[N];
int com, budget , idx ;
map<pair<int,int> , int > mem ;
int solve(int i ,int b , int q){
	if(i == idx+1)
		return q ;
	if(b<0)
		return -OO ;
	auto p = mp(i,b) ;
	if(mem.count(p))
		return mem[p] ;
	mem[p] = -OO  ;
	for(int j = 0 ; j < sz(adj[i]);j++){
		int ch1 = solve(i+1 , b - adj[i][j].ft , min(q,adj[i][j].sd)) ;
		mem[p] = max(mem[p] , ch1) ;
	}
	return mem[p] ;
}
int main() {
	Yahia74();
	int T;
		cin >> T;
		while (T--) {
			cin >> com >> budget;
			for (int i = 0; i <= 1004; ++i)
				adj[i].clear();
			mem.clear();
			idx = -1 ;
			map<string, int> mp;
			for (int i = 0; i < com; ++i) {
				string s, t;
				int quality, price;
				cin >> s >> t >> price >> quality;
				if (mp.find(s) == mp.end())
					mp[s] = ++idx;
				adj[mp[s]].pb(mp(price,quality));
			}
			cout << solve(0 , budget, OO ) << el ;
		}
	return 0;
}
/*























*/