← 返回题目列表

Codeforces · 1629/A

A. 下载更多 RAM

中文机器翻译题面 查看原题

您知道可以下载更多 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。