您知道可以下载更多 RAM 吗?有一家商店提供 $$$n$$$ 不同的软件,可以增加你的 RAM。第 $$$i$$$ 个 RAM 增加软件需要 $$$a_i$$$ GB 的内存来运行(暂时,一旦程序运行完毕,您就会收回 RAM),并为您提供额外的 $$$b_i$$$ GB 的 RAM(永久)。每个软件只能使用一次。您的电脑当前拥有 $$$k$$$ GB RAM。
请注意,如果 RAM 增加软件需要使用比您当前拥有的 RAM 更多 GB 的 RAM,则您无法使用该软件。
由于 RAM 是世界上最重要的东西,您想知道 RAM 的最大可能数量是多少?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 1000$$$)。接下来是两行,每行包含 $$$n$$$ 整数,描述数组 $$$a$$$ 和 $$$b$$$ ($$$1 \le a_i, b_i \le 1000$$$)。
输出
对于每个测试用例,输出一行,其中包含您可以实现的最大 RAM 量。
示例
输入 #1
4 3 10 20 30 10 9 100 10 5 1 1 1 5 1 1 1 1 1 1 1 5 1 2 2 2 2 2 100 100 100 100 100 5 8 128 64 32 16 8 128 64 32 16 8
输出 #1
29 6 1 256
注意
在第一个测试用例中,您最初只有足够的 RAM 来运行第三个软件,但这会将您的 RAM 增加到 $$$20$$$ GB,这样您就可以使用第一个软件,将 RAM 增加到 $$$29$$$ GB。剩下的唯一软件需要 $$$30$$$ GB RAM,所以你必须停在这里。
在第二个测试用例中,您可以使用每个软件仅需要 $$$1$$$ GB RAM 即可运行的第一个、第二个、第四个和第五个软件,将 RAM 增加到 $$$5$$$ GB,然后使用最后一个剩余的软件将 RAM 增加到 $$$6$$$ GB。
在第三个测试用例中,所有软件都需要超过 $$$1$$$ GB 的 RAM 才能运行,因此您拥有的 RAM 量保持在 $$$1$$$ GB。