Problem3039--组装电脑[Assemble,LA3971]

3039: 组装电脑[Assemble,LA3971]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

最近你的团队注意到你用于编程训练的电脑性能跟不上了，所以他们建议你买一个新电脑。
为了能够获得一台理想的电脑，你准备购买一些电脑配件然后自己组装成一台电脑，因此每一种类型的电脑配件你都需要买。
关键问题就是该购买哪些配件呢？众所周知，最弱的电脑配件的质量水平决定了电脑的质量的水平，所以你希望以最低的质量来最大化配件质量，这样才不会超过预算。

Input

第一行是一个正整数，表示测试数据组数，最大不超过100。
每组测试数据，第一行，两个正整数n和b，表示电脑配件的个数以及预算费用（1≤n≤1000，1≤b≤1000000000）
接下来n行，每行的格式是“配件类型type 配件名称name 配件价格price 配件质量quality”，配件类型type和配件名称name都是字符串，字符串只包含字符、数字和下划线，字符串的长度不超过20个字符
配件价格price和配件质量quality都是整数（0≤price≤1000000；0≤quality≤1000000000），quality的值越大代表质量越好。

Output

对于每组测试数据，输出一个整数，表示配件最小质量的最大值

Sample Input Copy 

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 Copy 

9

Source/Category

二分查找 贪心 UVA level6 
[Submit] [Status]