#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

#define VI vector<int>
#define int64 long long
#define VVI vector <vector<int> >

#define SZ(a) a.size()
#define MP make_pair
#define PB push_back
#define ALL(a) a.begin(), a.end()
#define CLA(a) memset(a, 0, sizeof(a))
#define FOR(i,n) for (int i = 0; i < int(n); i++)
#define FORR(i,n) for (int i = n - 1; i >=0; i--)
#define REP(n) for (int _foo = n - 1; _foo >= 0; _foo--)

#define INF 1000000000

int ri() {int t; scanf("%d", &t); return t;}
void pi(int n){printf("%d\n", n);}

struct comp{
	int type, cost, quality;
}a[1024];

int n;

int chp[1024], b, res, k;

char s1[1000], s2[1000];

int can(int what)
{
	if (what <= 0) return 1;
	CLA(chp);
	FOR(i,n)
		if (a[i].quality >= what)
			if (!chp[a[i].type] || chp[a[i].type] > a[i].cost + 1)
				chp[a[i].type] = a[i].cost + 1;
	int64 sum = 0;
	for (int i = 1; i <= k; i++)
		sum += chp[i] ? chp[i] - 1 : (int64)INF + INF;
	return sum <= b;
}

int main()
{
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	REP(ri())
	{
		n = ri();
		b = ri();
		map <string, int> mp; k = 0;
		FOR(i, n)
		{
			scanf("%s %s %d %d", s1, s2, &a[i].cost, &a[i].quality);
			string ss(s1);
			if (!mp[ss]) mp[ss] = ++k;
			a[i].type = mp[ss];
		}
		int l = 0, r = 2000000000, m;
		while (r - l > 1)
		{
			m = (r + l) / 2;
			if (can(m))
				l = m;
			else
				r = m - 1;
		}
		res = can(l + 3) ? l + 3 :can(l + 2) ? l + 2 : can(l + 1) ? l + 1 : can(l) ? l : can(l - 1) ? l - 1 : l - 2;
		pi(res);
	}

}
