#include <bits/stdc++.h>

 using namespace std;

 const int maxn=+;

 int n,b,num;

 char typec[],namec[];

 int price,quality;

 int fp[maxn][maxn],fq[maxn][maxn],m[maxn];

 vector <string> tp;

 void trans()

 {

     int i,j,l;

     string s=typec;

     l=tp.size();

     for(i=;i<l;i++)

     {

         if(tp[i]==s)

         {

             m[i+]++;

             fp[i+][m[i+]]=price;

             fq[i+][m[i+]]=quality;

             return;

         }

     }

     tp.push_back(s);

     m[l+]++;

     fp[l+][m[l+]]=price;

     fq[l+][m[l+]]=quality;

 }

 int check(int qu)

 {

     int i,j,sum=;

     for(i=;i<=num;i++)

     {

         int mi=;

         for(j=;j<=m[i];j++)

         {

             if(fq[i][j]>=qu && fp[i][j]<mi)

                 mi=fp[i][j];

         }

         if(mi==)

             return ;

         sum+=mi;

     }

     if(sum<=b)

         return ;

     else

         return ;

 }

 int main()

 {

     int T;

     int i,j;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d %d",&n,&b);

         memset(m,,sizeof(m));

         tp.clear();

         for(i=;i<=n;i++)

         {

             scanf("%s %s %d %d",typec,namec,&price,&quality);

             trans();

         }

         num=tp.size();

         int l=,r=;

         while(l+<r)

         {

             int mid=(l+r)/;

             if(check(mid))

             {

                 l=mid;

             }

             else

             {

                 r=mid;

             }

         }

         printf("%d\n",l);

     }

     return ;

 }