简单版和困难版之间的唯一区别是你可以传送到的位置。
考虑数轴上的点 $$$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$$$。
在第三个测试用例中,您没有足够的硬币来使用任何传送器,因此答案为零。