题目描述

本题的简单版与困难版的唯一区别在于你可以传送到的位置。

考虑数轴上的点 $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$。

输出格式

对于每组测试数据，输出你最多能使用多少个传送器。

样例

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

2
3
0
1
3
2
1
1
2
2

样例说明

在第一个测试用例中，你可以向右移动一格，使用第 $1$ 个传送器传送到点 $n+1$，再向左移动一格，使用第 $5$ 个传送器。你剩下 $6-1-1-1-1=2$ 个金币，无论你传送到哪里，都不足以再使用一个传送器。你共使用了两个传送器，所以答案是 $2$。

在第二个测试用例中，你向右移动四格并使用传送器传送到 $n+1$，然后向左移动三格并使用第 $6$ 个传送器传送到 $n+1$，最后再向左移动四格并使用传送器。总花费为 $4+6+3+4+4+9=30$，你使用了三个传送器。

在第三个测试用例中，你的金币不足以使用任何传送器，所以答案是 $0$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1791G2，英文题名 Teleporters (Hard Version)。