#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst double eps=1e-10;const int INF=1000000000;const int maxn=1000+10;int T,n,b,cnt;struct component{    int price,quality;    component(int x,int y):price(x),quality(y) {}};map<string,int>id;int getid(string str){    if(!id.count(str)) id[str]=cnt++;    return id[str];}vector<component>v[maxn];void ini(){    cnt=0;    for(int i=0; i<n; i++) v[i].clear();    id.clear();}bool ok(int x){    LL sum=0;    for(int i=0; i<cnt; i++)    {        int cheap=b+1;        int siz=v[i].size();        for(int j=0; j<siz; j++)        {            if(v[i][j].quality>=x)            {                cheap=min(cheap,v[i][j].price);            }        }        if(cheap==b+1) {return false;}        else sum+=(LL)cheap;    }    if(sum<=(LL)b) {return true;}    else {return false;}}int main(){    //freopen("in1.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&b);        ini();        int maxqq=-1;        for(int i=0; i<n; i++)        {            string type,name;            int pp,qq;            cin>>type>>name>>pp>>qq;            maxqq=max(qq,maxqq);            v[getid(type)].push_back(component(pp,qq));        }        int L=0,R=maxqq;        while(L<R)        {            //cout<<L<<"hhh"<<R<<endl;            int M=L+(R-L+1)/2;            /*这么写是向上进位的写法，而M=(L+R)/2是            向下取整的写法，写成哪个要根据实际            情况（也就是二分的写法）来，            本题如果写成第二个就会出现死循环，比如L=1,R=2            时就是。*/            if(ok(M))            {                L=M;            }            else            {                R=M-1;            }        }        printf("%d\n",L);    }    //fclose(stdin);    //fclose(stdout);    return 0;}