C. Fish买电脑
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 14 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
在暑假集训一段时间后，Fish决定要买一台电脑了,想要成为一名合格的ACMer没有一台好的电脑是不行的，可是Fish对电脑硬件方面一窍不通，于是找来Rexdf帮忙，Rexdf可是软硬件通吃，装一台电脑更是不在话下了。为了适应需求，他们打算购买电脑的各零件，然后回来自己组装。
对于电脑中的每一个零件他们买且只买一个。现在的问题是每一种零件都有好多品牌，品牌下又分好多型号，不同型号的价钱不等，同时它们的质量也不一样。而整个电脑的质量取决于各零件中质量最差的那个。所以我们需要在不超出预支金额的情况下，尽量使得质量最差的那个零件的质量最大化，这样我们购买的电脑总体质量才不至于太低。
对于电脑中的每一个零件他们买且只买一个。现在的问题是每一种零件都有好多品牌，品牌下又分好多型号，不同型号的价钱不等，同时它们的质量也不一样。而整个电脑的质量取决于各零件中质量最差的那个。所以我们需要在不超出预支金额的情况下，尽量使得质量最差的那个零件的质量最大化，这样我们购买的电脑总体质量才不至于太低。
Input
输入数据的第一行有一个整数T，代表测试数据的组数。接下来有T组测试数据。
对于每组测试数据：
第一行有两个整数n和M，表示需要购买的零件种类和Fish买电脑预支的金额。
接下来的n行代表每一种零件的信息，这些信息以”类型 型号 价格 质量”的格式给出，他们之间以一个空格分隔。这四个属性中：
“类型”为一个字符串，仅包含小写字母。不超过20个字符。
“型号”为一个字符串，包含字母，数字，下划线。不超过20个字符。
“价格”为一个正整数。
“质量”为一个正整数，数值越大则质量越高。
范围：
T ≤ 100
1 ≤ n ≤ 1 000
1 ≤ M ≤ 1 000 000 000
0 ≤ price ≤ 1 000 000
0 ≤ quality ≤ 1 000 000 000
对于每组测试数据：
第一行有两个整数n和M，表示需要购买的零件种类和Fish买电脑预支的金额。
接下来的n行代表每一种零件的信息，这些信息以”类型 型号 价格 质量”的格式给出，他们之间以一个空格分隔。这四个属性中：
“类型”为一个字符串，仅包含小写字母。不超过20个字符。
“型号”为一个字符串，包含字母，数字，下划线。不超过20个字符。
“价格”为一个正整数。
“质量”为一个正整数，数值越大则质量越高。
范围：
T ≤ 100
1 ≤ n ≤ 1 000
1 ≤ M ≤ 1 000 000 000
0 ≤ price ≤ 1 000 000
0 ≤ quality ≤ 1 000 000 000
Output
对于每组测试数据，输出一个整数并换行。这个整数代表新电脑的最大质量（即最小的质量最大是多少）
Sample Input
1 18 800 processor 3500_MHz 66 5 processor 4200_MHz 103 7 processor 5000_MHz 156 9 processor 6000_MHz 219 12 memory 1_GB 35 3 memory 2_GB 88 6 memory 4_GB 170 12 mainbord all_onboard 52 10 harddisk 250_GB 54 10 harddisk 500_FB 99 12 casing midi 36 10 monitor 17_inch 157 5 monitor 19_inch 175 7 monitor 20_inch 210 9 monitor 22_inch 293 12 mouse cordless_optical 18 12 mouse microsoft 30 9 keyboard office 4 10
Sample Output
9
Author
Source
developing schools contest 5