简单版和困难版之间的唯一区别是你可以传送到的位置。
考虑数轴上的点 $$$0,1,\dots,n+1$$$。每个点 $$$1,2,\dots,n$$$ 上都有一个传送器。在 $$$i$$$ 点,您可以执行以下操作:
- 向左移动一个单位:花费 $$$1$$$ 硬币。
- 向右移动一个单位:花费 $$$1$$$ 硬币。
- 在 $$$i$$$ 点使用传送器(如果存在):需要花费 $$$a_i$$$ 硬币。因此,您可以选择是否传送到点 $$$0$$$ 或点 $$$n+1$$$。一旦使用传送器,就无法再次使用。
您有 $$$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 3 0 1 3 2 1 1 2 2
注意
在第一个测试用例中,您可以向右移动一个单位,在索引 $$$1$$$ 处使用传送器并传送到指向 $$$n+1$$$,向左移动一个单位并在索引 $$$5$$$ 处使用传送器。你只剩下 $$$6-1-1-1-1 = 2$$$ 硬币,无论你传送到哪里,你都没有足够的硬币来使用另一个传送器。你使用了两个传送器,所以答案是两个。
在第二个测试用例中,您向右走四个单位并使用传送器前往 $$$n+1$$$,然后向左走三个单位并使用索引 $$$6$$$ 处的传送器前往 $$$n+1$$$,最后向左走四次并使用传送器。总成本为 $$$4+6+3+4+4+9 = 30$$$,并且您使用了三个传送器。
在第三个测试用例中,您没有足够的硬币来使用任何传送器,因此答案为零。