1 //#define LOCAL 2 #include <vector> 3 #include <cstdio> 4 #include <string> 5 #include <map> 6 using namespace std; 7  8 int cnt;    //组件的类型数 9 map<string, int> id;    //将组件类型的名字与编号对应起来10 int ID(string s)    //求类型s的编号11 {12     if(!id.count(s))    id[s] = cnt++;13     return id[s];14 }15 const int maxn = 1000 + 5;16 struct Component17 {18     int price;19     int quality;20 };21 int n, b;22 vector<Component> comp[maxn];23 24 bool ok(int q)25 {//品质不小于q的组件能否组成不超过b元的电脑26     int sum = 0;27     for(int i = 0; i < cnt; ++i)28     {29         int cheapest = b + 1, m = comp[i].size();30         for(int j = 0; j < m; ++j)31             if(comp[i][j].quality >= q)32                 cheapest = min(cheapest, comp[i][j].price);33                 //选择品质因子不小于p的最便宜的配件34         if(cheapest > b)    return false;35         sum += cheapest;36         if(sum > b)    return false;37     }38     return true;39 }40 41 int main(void)42 {43     #ifdef LOCAL44         freopen("3971in.txt", "r", stdin);45     #endif46 47     int T;48     scanf("%d", &T);49     while(T--)50     {51         scanf("%d%d", &n, &b);52         cnt = 0;53         for(int i = 0; i < n; ++i)    comp[i].clear();54         id.clear();55 56         int maxq = 0;57         for(int i = 0; i < n; ++i)58         {59             char type[30], name[30];60             int p, q;61             scanf("%s%s%d%d", type, name, &p, &q);62             maxq = max(maxq, q);63             comp[ID(type)].push_back((Component) {p, q});64         }65 66         int L = 0, R = maxq;67         while(L < R)68         {69             int M = L + (R - L + 1) / 2;70             if(ok(M))71                 L = M;72             else73                 R = M - 1;74         }75         printf("%d\n", L);76     }77     return 0;78 }