题目描述

POJ 3497

购买一台最新型计算机是琪儿的近期目标。但是由于计算机价格昂贵，她只能用一定的预算去买各种计算机的组件，组件每种买一个，其中电脑组件都有品质和价格两个参数。

众所周知，计算机的品质取决于它所有组件中最差的品质部件，因此，如何在不超过预算的情况下，让买到的计算机品质最大呢？

输入格式

第一行为一个整数$\red{N}$，表示测试组数，$\red{N}$不超过$\red{100}$。

每组数据第一行有两个数，即组件数和预算（$\red{1≤}$组件数$\red{≤1 000}$， $\red{1≤}$预算$\red{≤1 000 000 000}$）。

以下各行为组件的类型、名称、价格（$\red{0≤}$价格$\red{≤1 000 000}$）、质量（$\red{0≤}$质量$\red{≤1 000 000 000}$）。

输出格式

每组测试数据输出一行，即能买到的所有组件的最大品质值。

样例

输入样例

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

输出样例

9