#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 main() {
Yahia74();
int T;
cin >> T;
while (T--) {
int com, budget;
int numOfComp = 1;
map<string, int> mp;
cin >> com >> budget;
for (int i = 0; i <= 1004; ++i)
adj[i].clear();
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] = numOfComp++;
adj[mp[s]].pb(mp(price,quality));
}
for (int i = 1; i < numOfComp; i++) {
sort(all(adj[i])); // sorting in price order then quality
for (int j = 1; j < sz(adj[i]); j++) {
while (adj[i][j].sd <= adj[i][j - 1].sd && j < sz(adj[i]))
adj[i].erase(adj[i].begin() + j); // erase all unsafely components that have higher price with lower quality
}
}
set<int> totQ ;
for (int i = 1; i < numOfComp; i++)
for (int j = 0; j < sz(adj[i]); j++)
totQ.insert(adj[i][j].sd);
int idx[1005]={}; // pointer in each components refer to current quality so far.
int ans = -1;
bool flag = false;
for (auto i : totQ) {
ll tot = 0;
for (int j = 1; j < numOfComp; j++) {
while (adj[j][idx[j]].sd < i && idx[j] < sz(adj[j]))
idx[j]++;
if (idx[j] == sz(adj[j])) { // break if I reach the end of any components because that is the maximum I will get
flag = true;
break;
}
tot += (ll) adj[j][idx[j]].ft;
}
if (tot > budget || flag)
break;
ans = i;
}
cout << ans << el;
}
return 0;
}
/*
*/
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgZWwgICAgICAJJ1xuJwojZGVmaW5lIGZ0IAkJCWZpcnN0CiNkZWZpbmUgc2QgCQkJc2Vjb25kCiNkZWZpbmUgbXAoeCx5KSAgCW1ha2VfcGFpcigoeCksKHkpKQojZGVmaW5lIHBiKHgpICAgIAlwdXNoX2JhY2soKHgpKQojZGVmaW5lIGFsbCh2KSAgCSgodikuYmVnaW4oKSksKCh2KS5lbmQoKSkKI2RlZmluZSBzeih4KSAgCQkoKGludCkgKHgpLnNpemUoKSkKI2RlZmluZSBjbHIoYSxiKQltZW1zZXQoYSxiLHNpemVvZihhKSkKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnZvaWQgWWFoaWE3NCgpIHsKI2lmbmRlZiBPTkxJTkVfSlVER0UKCWZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOyAvL2ZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiNlbmRpZgoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4udGllKG51bGxwdHIpLCBjb3V0LnRpZShudWxscHRyKTsKfQpjb25zdCBpbnQgTiA9IDFlMyArIDc0LCBPTyA9IDB4M2YzZjNmM2YsIE1PRCA9IChpbnQpIDFlOSArIDc7Cgp2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBhZGpbTl07CmludCBtYWluKCkgewoJWWFoaWE3NCgpOwoJaW50IFQ7CgljaW4gPj4gVDsKCXdoaWxlIChULS0pIHsKCQlpbnQgY29tLCBidWRnZXQ7CgkJaW50IG51bU9mQ29tcCA9IDE7CgkJbWFwPHN0cmluZywgaW50PiBtcDsKCQljaW4gPj4gY29tID4+IGJ1ZGdldDsKCQlmb3IgKGludCBpID0gMDsgaSA8PSAxMDA0OyArK2kpCgkJCWFkaltpXS5jbGVhcigpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgY29tOyArK2kpIHsKCQkJc3RyaW5nIHMsIHQ7CgkJCWludCBxdWFsaXR5LCBwcmljZTsKCQkJY2luID4+IHMgPj4gdCA+PiBwcmljZSA+PiBxdWFsaXR5OwoJCQlpZiAobXAuZmluZChzKSA9PSBtcC5lbmQoKSkKCQkJCW1wW3NdID0gbnVtT2ZDb21wKys7CgkJCWFkalttcFtzXV0ucGIobXAocHJpY2UscXVhbGl0eSkpOwoJCX0KCQlmb3IgKGludCBpID0gMTsgaSA8IG51bU9mQ29tcDsgaSsrKSB7CgkJCXNvcnQoYWxsKGFkaltpXSkpOyAvLyBzb3J0aW5nIGluIHByaWNlIG9yZGVyIHRoZW4gcXVhbGl0eQoJCQlmb3IgKGludCBqID0gMTsgaiA8IHN6KGFkaltpXSk7IGorKykgewoJCQkJd2hpbGUgKGFkaltpXVtqXS5zZCA8PSBhZGpbaV1baiAtIDFdLnNkICYmIGogPCBzeihhZGpbaV0pKQoJCQkJCWFkaltpXS5lcmFzZShhZGpbaV0uYmVnaW4oKSArIGopOyAvLyBlcmFzZSBhbGwgdW5zYWZlbHkgY29tcG9uZW50cyB0aGF0IGhhdmUgaGlnaGVyIHByaWNlIHdpdGggbG93ZXIgcXVhbGl0eQoJCQl9CgkJfQoJCXNldDxpbnQ+IHRvdFEgOwoJCWZvciAoaW50IGkgPSAxOyBpIDwgbnVtT2ZDb21wOyBpKyspCgkJCWZvciAoaW50IGogPSAwOyBqIDwgc3ooYWRqW2ldKTsgaisrKQoJCQkJdG90US5pbnNlcnQoYWRqW2ldW2pdLnNkKTsKCQlpbnQgaWR4WzEwMDVdPXt9OyAvLyBwb2ludGVyIGluIGVhY2ggY29tcG9uZW50cyByZWZlciB0byBjdXJyZW50IHF1YWxpdHkgc28gZmFyLgoJCWludCBhbnMgPSAtMTsKCQlib29sIGZsYWcgPSBmYWxzZTsKCQlmb3IgKGF1dG8gaSA6IHRvdFEpIHsKCQkJbGwgdG90ID0gMDsKCQkJZm9yIChpbnQgaiA9IDE7IGogPCBudW1PZkNvbXA7IGorKykgewoJCQkJd2hpbGUgKGFkaltqXVtpZHhbal1dLnNkIDwgaSAmJiBpZHhbal0gPCBzeihhZGpbal0pKQoJCQkJCWlkeFtqXSsrOwoJCQkJaWYgKGlkeFtqXSA9PSBzeihhZGpbal0pKSB7IC8vIGJyZWFrIGlmIEkgcmVhY2ggdGhlIGVuZCBvZiBhbnkgY29tcG9uZW50cyBiZWNhdXNlIHRoYXQgaXMgdGhlIG1heGltdW0gSSB3aWxsIGdldAoJCQkJCWZsYWcgPSB0cnVlOwoJCQkJCWJyZWFrOwoJCQkJfQoJCQkJdG90ICs9IChsbCkgYWRqW2pdW2lkeFtqXV0uZnQ7CgkJCX0KCQkJaWYgKHRvdCA+IGJ1ZGdldCB8fCBmbGFnKQoJCQkJYnJlYWs7CgkJCWFucyA9IGk7CgkJfQoJCWNvdXQgPDwgYW5zIDw8IGVsOwoJfQoJcmV0dXJuIDA7Cn0KLyoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgogKi8K