最近，你的队伍注意到你们用来练习程序设计竞赛的电脑已经不够好了。因此，你们决定买一台新电脑。

为了组装出最符合你们需求的理想电脑，你们决定购买独立的配件并自己组装。每种类型的配件你们需要恰好购买一个。

问题在于应该购买哪些配件。众所周知，一台电脑的性能（质量）取决于其最差配件的性能。因此，你们希望在不超过预算的前提下，最大化性能最低的配件的性能。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。对于每个测试用例：

• 一行包含两个整数：$1 \le n \le 1\,000$，表示可用配件的数量，以及 $1 \le b \le 1\,000\,000\,000$，表示你的预算。
• 接下来的 $n$ 行，每行格式为：type name price quality，其中 type 是表示配件类型的字符串，name 是表示配件唯一名称的字符串，price 是一个整数（$0 \le \text{price} \le 1\,000\,000$）表示该配件的价格，quality 是一个整数（$0 \le \text{quality} \le 1\,000\,000\,000$）表示该配件的性能（质量，越高越好）。字符串仅包含字母、数字和下划线，且最大长度为 20 个字符。

保证在预算内总是可以组装出一台电脑。

输出格式

对于每个测试用例：

• 输出一行，包含一个整数：可能的最大性能。

样例

输入样例 1

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

输出样例 1

9