2068: 宝典2第一章电脑组装

【问题描述】电脑组装(Assemble.cpp/c/pas)　POJ 3497

魔法世界的魔法师们近来讨论话题最多的无疑是最新型量子计算机的上市，量子计算机运算速度惊人，例如求解一个亿亿亿级变量的方程组，即便是用世界上最快的超级计算机也至少需要几百年。而量子计算机十秒钟就可解决。所以对于一直信奉“工欲善其事，必先利其器。”的张琪曼来说，购买一台最新型量子计算机是她的近期目标。但是由于量子计算机价格昂贵，她只能用一定的预算去买各种量子计算机的组件，组件每种买一个，其中电脑组件都有品质和价格两个参数。

求在不超过预算的情况下，能买到的所有组件的最差品质的最大值是多少。

【输入格式】

第一行为一个整数Ｎ，表示测试组数，Ｎ不超过100。

每组数据第一行有两个数，即组件数和预算，其中1≤组件数≤1 000， 1≤预算≤1 000 000 000。

以下各行为组件的类型、名称、价格、质量。

【输出格式】

能买到的所有组件的最差品质的最大值。每组测试数据为一行。

【输入样例】

1　　（表示测试组数，不超过100组）

18 800 (表示1≤组件数≤1 000， 1≤预算≤1 000 000 000)

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