思路：对于每个种类，买符合条件的每种取最小值，二分答案

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000
int A,B,kind;
map<string,bool>f;
int p[MAXN],q[MAXN];
string v[MAXN],b; 
bool check(int x)
{
	int K=0;
	long long sum=0;
	map<string,int>Price=map<string,int>();
	map<string,bool>F=map<string,bool>();
	for(int i=1;i<=A;i++)
	    Price[v[i]]=0x3f3f3f3f;
	for(int i=1;i<=A;i++)
		if(q[i]>=x)
	        Price[v[i]]=min(Price[v[i]],p[i]);
	for(int i=1;i<=A;i++)
	    if(!F[v[i]])
	    {
	    	F[v[i]]=1;
	    	sum+=Price[v[i]];
	        K++;
		}
    if(sum>B||K<kind)
        return 0;
    return 1;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>A>>B;
		for(int i=1;i<=A;i++)
		{
			cin>>v[i]>>b;
			if(!f[v[i]])
			    kind++;
			f[v[i]]=1;
			cin>>p[i]>>q[i];
		}
		long long l=0,r=1000000000000,ans;
		while(l<=r)
		{
			long long mid=l+r>>1;
			if(check(mid))
			    l=mid+1,ans=mid;
			else
			    r=mid-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}