#include<iostream>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<string>

using namespace std;

const int maxn = 1e3 + ;

int cnt;

map<string, int>ss;

int id(string x){

    if (!ss.count(x))ss[x] = cnt++;

    return ss[x];

}

struct node{ int x, y; };

vector<node>comp[maxn];

int t, n, b;

//品质不小于x的组件能否组装为不超过b的电脑

bool ok(int x){

    int sum = ;

    for (int i = ; i < cnt; ++i){

        int pest = b + , m = comp[i].size();

        for (int j = ; j < m;++j)        //找大于x的最小值

        if (comp[i][j].y >= x)pest = min(pest, comp[i][j].x);

        if (pest == b + )return ;

        sum += pest;

        if (sum>b)return ;

    }

    return ;

}

int main(){

    cin >> t;

    while (t--){

        cin >> n >> b;

        //初始化

        cnt = ;

        for (int i = ; i < n; ++i)comp[i].clear();

        ss.clear();            int maxq = ;

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

            //初始化

            string type, name;    int x, y;

            cin >> type >> name >> x >> y;    maxq = max(maxq, y);

            comp[id(type)].push_back(node{ x, y });

        }

        int L = , R = maxq;

        while (L < R){

        //    cout << "L=" << L << "  R=" << R << endl;

            int M = L + (R - L + ) / ;

            if (ok(M))L = M;    else R = M - ;

        }

        cout << L << endl;

    }

    return ;

}