#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 #define MAXL 25

 #define MAXN 1005

 #define INF  1000000000

 typedef struct {

     char name[MAXL];

     int p, q;

 } comp_st;

 comp_st comps[MAXN];

 int t, n, b;

 int ns[MAXN], nn;

 bool comp(comp_st a, comp_st b) {

     int tmp = strcmp(a.name, b.name);

     if (tmp == )

         return a.q > b.q;

     else

         return tmp < ;

 }

 bool chk(int x) {

     int i, j;

     int sum = , min;

     for (i=; i<nn; ++i) {

         min = INF;

         for (j=ns[i]; j<ns[i+]; ++j) {

             if (comps[j].q>=x && min>comps[j].p)

                 min = comps[j].p;

         }

         /* pay attention to here.*/

         if (min == INF)

             return false;

         sum += min;

     }

     return sum<=b;

 }

 int main() {

     int i, min, max, mid, v;

     char str[MAXL];

     scanf("%d", &t);

     while (t--) {

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

         min = INF;

         max = ;

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

             scanf("%s %s %d %d", comps[i].name, str, &comps[i].p, &comps[i].q);

             if (comps[i].q < min) min = comps[i].q;

             if (comps[i].q > max) max = comps[i].q;

         }

         sort(comps, comps+n, comp);

         ns[] = ;

         for (nn=,i=; i<n; ++i) {

             if (strcmp(comps[i-].name, comps[i].name) != )

                 ns[++nn] = i;

         }

         ns[++nn] = n;

         v = ;

         while (min <= max) {

             mid = (min+max)/;

             if ( chk(mid) ) {

                 v = mid;

                 min = mid+;

             } else {

                 max = mid-;

             }

         }

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

     }

     return ;

 }