#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;#define maxn 1005#define maxl 25struct Elem{ int id, quality, price;}elem[maxn];int n, budget;char name[maxn][maxl];int tot;bool vis[maxn];int f[maxn];bool operator < (const Elem &a, const Elem &b){ return a.price < b.price;}int getid(char *st){ for (int i = 0; i < tot; i++) if (strcmp(st, name[i]) == 0) return i; strcpy(name[tot], st); return tot++;}void input(){ char st[maxl]; scanf("%d%d", &n, &budget); tot = 0; for (int i = 0; i < n; i++) { scanf("%s", st); elem[i].id = getid(st); scanf("%s%d%d", st, &elem[i].price, &elem[i].quality); }}bool ok(int a){ int cnt = 0; long long temp = 0; memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) if (!vis[elem[i].id] && elem[i].quality >= a) { vis[elem[i].id] = true; cnt++; temp += elem[i].price; } return temp <= budget;}int binarysearch(){ int l = 0; int r = 1000000000; memset(f, 0, sizeof(f)); for (int i = 0; i < n; i++) f[elem[i].id] = max(f[elem[i].id], elem[i].quality); for (int i = 0; i < tot; i++) r = min(r, f[i]); while (l < r) { int mid = (l + r + 1) / 2; if (!ok(mid)) r = mid - 1; else l = mid; } return l;}int main(){ int t; scanf("%d", &t); while (t--) { input(); sort(elem, elem + n); int ans = binarysearch(); printf("%dn", ans); } return 0;}
