← 返回题目列表

Codeforces · 1791/G1

G1. 传送器(简单版)

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

简单版和困难版之间的唯一区别是你可以传送到的位置。

考虑数轴上的点 $$$0, 1, \dots, n$$$。每个点 $$$1, 2, \dots, n$$$ 上都有一个传送器。在 $$$i$$$ 点,您可以执行以下操作:

- 向左移动一个单位:花费 $$$1$$$ 硬币。
- 向右移动一个单位:花费 $$$1$$$ 硬币。
- 在 $$$i$$$ 点使用传送器(如果存在):需要花费 $$$a_i$$$ 硬币。结果,您传送到点$$$0$$$。一旦使用传送器,就无法再次使用。

您有 $$$c$$$ 硬币,并且您从 $$$0$$$ 开始。您最多可以使用多少个传送器?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^9$$$) — 分别是数组的长度和你拥有的硬币数量。

以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 使用传送器的成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出您可以使用的传送器的最大数量。

示例

输入 #1

10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000

输出 #1

2
2
0
1
2
2
1
1
1
2

注意

在第一个测试用例中,您可以向右移动一个单位,使用索引 $$$1$$$ 处的传送器并传送到 $$$0$$$,向右移动两个单位并使用索引 $$$2$$$ 处的传送器。您剩下 $$$6-1-1-2-1 = 1$$$ 硬币,您没有足够的硬币来使用另一个传送器。你使用了两个传送器,所以答案是两个。

在第二个测试用例中,您向右移动四个单位并使用传送器前往 $$$0$$$,然后向右移动六个单位并使用索引 $$$6$$$ 处的传送器前往 $$$0$$$。总成本为 $$$4+6+6+4 = 20$$$。您剩下 $$$12$$$ 硬币,但不足以到达任何其他传送器并使用它,所以答案是 $$$2$$$。

在第三个测试用例中,您没有足够的硬币来使用任何传送器,因此答案为零。