魔法世界的魔法师们近来讨论话题最多的无疑是最新型量子计算机的上市，量子计算机运算速度惊人，例如求解一个亿亿亿级变量的方程组，即便是用世界上最快的超级计算机也至少需要几百年。而量子计算机十秒钟就可解决。所以对于一直信奉“工欲善其事，必先利其器。”的张琪曼来说，购买一台最新型量子计算机是她的近期目标。但是由于量子计算机价格昂贵，她只能用一定的预算去买各种量子计算机的组件，组件每种买一个，其中电脑组件都有品质和价格两个参数。
求在不超过预算的情况下，能买到的所有组件的最差品质的最大值是多少。
魔法世界的魔法师们近来讨论话题最多的无疑是最新型量子计算机的上市，量子计算机运算速度惊人，例如求解一个亿亿亿级变量的方程组，即便是用世界上最快的超级计算机也至少需要几百年。而量子计算机十秒钟就可解决。所以对于一直信奉“工欲善其事，必先利其器。”的张琪曼来说，购买一台最新型量子计算机是她的近期目标。但是由于量子计算机价格昂贵，她只能用一定的预算去买各种量子计算机的组件，组件每种买一个，其中电脑组件都有品质和价格两个参数。
求在不超过预算的情况下，能买到的所有组件的最差品质的最大值是多少。
第一行为一个整数Ｎ，表示测试组数，Ｎ不超过100。
每组数据第一行有两个数，即组件数和预算，其中1≤组件数≤1 000， 1≤预算≤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 109