205017 - 电脑组装

琪儿要用一定的预算去买各种电脑组件以组装电脑，组件每种买一个，其中电脑组件都有品质和价格两个参数。 众所周知，电脑品质取决于它所有组件中最差的品质部件，因此，如何在不超过预算的情况下，使组装好的电脑品质最大呢？

Input

输入第1行为一个整数N，表示测试组数，N不超过100。 每组数据第一行有两个数，即组件数和预算（1≤组件数≤1 000， 1≤预算≤1 000 000 000）。 以下各行为组件的类型、名称、价格（0≤价格≤1 000 000）、质量（0≤质量≤1 000 000 000）。

Output

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

Examples

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

Output

9
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题