问题 5461. -- 组装电脑-【2014暑期训练】T2Day2T2

5461: 组装电脑-【2014暑期训练】T2Day2T2

时间限制: 1 Sec  内存限制: 256 MB
献花: 1  解决: 0
[献花][花圈]

题目描述

组装电脑 

【问题描述】

天哥决定组装一台超级电脑,预算b元大钞购买各类配件。现给出n各配件各自的种类、品质因子和价格,要求每种类型的配件各买一个,总费用不超过b,且“品质最差配件”的品质因子应尽量大。

【文件输入】

输入文件assemble.in。

第一行为两个正整数n(1<=n<=50000)和b(1<=b<=10^9),即配件的数量和预算。

以下每行描述一个配件,依次为种类、名称、价格和品质因子。其中价格为不超过10^6的非负整数,品质因子是不超过10^9的非负整数,种类和名称是由不超过20个字母、数字、下划线组成,输出保证有解。

【文件输出】

输出文件assemble.out。

输出购买的配件中最小品质因子的最大值。

【输入样例】

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

【输出样例】

9

【数据规模】

30%的数据 n<=20。

50%的数据n<=100。

70%的数据n<=1000。

100%的数据n<=50000。

配件种类不超过4000。

输入

输出

提示

来源

[献花][花圈]