#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n,b,cnt;
char op1[50];char op2[50];
struct node{int x,q;node(int x,int q):x(x),q(q){}};
typedef long long ll;
const int maxn=1e3+7;
vector<node> things[maxn];
int mxcheap[maxn][maxn];
bool cmp(node a,node b){return (a.q!=b.q)?a.q<b.q:a.x<b.x;}
void init(){int i;for(i=0;i<maxn;++i) things[i].clear();}
void Sort(){int i;for(i=0;i<cnt;++i) sort(things[i].begin(),things[i].end(),cmp);}
bool check(int key){int i;ll sum=0;
    for(i=0;i<cnt;++i){
        int left=0,right=things[i].size()-1,mid;
        while(left<=right){
            mid=(left+right)>>1;
            if(things[i][mid].q<key) left=mid+1;else right=mid-1;
        }
        if(right+1<things[i].size()&&things[i][right+1].q>=key) right++;
        if(left>things[i].size()-1) {
        return false;}
        sum+=mxcheap[i][right]; 
    }
    return (sum>b)?false:true;}
int main(){

    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&b);init();
        int i,j,x,q,lq=-1,rq=-1;cnt=0;
        map<string,int> mp;
        for(i=0;i<n;++i){
            scanf("%s%s%d%d",op1,op2,&x,&q);
            if(!mp.count(string(op1))){
                mp[string(op1)]=cnt++;
            }
            things[mp[string(op1)]].push_back(node(x,q));
            rq=(rq==-1)?q:max(q,rq);
            lq=(lq==-1)?q:min(q,lq);
        }
        Sort();
        for(i=0;i<cnt;++i){
            mxcheap[i][things[i].size()-1]=things[i].back().x;
            for(j=things[i].size()-2;j>=0;--j){
                mxcheap[i][j]=min(things[i][j].x,mxcheap[i][j+1]);
            }
        }
        int left=lq,right=rq,mid,ans=-1;
        while(left<=right){
            mid=(left+right)>>1;
            if(check(mid)){left=mid+1;}
            else{right=mid-1;}
        }
        if(check(right+1)) right++;
        printf("%d\n",right);
    }
    return 0;
}