CF1791G1 Teleporters (Easy Version)

本题的简单版与困难版的唯一区别在于你可以传送到的位置。 考虑数轴上的点 $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$ 个传送器并传送回 $0$ 点，再向右移动两格，使用第 $2$ 个传送器。你剩下 $6-1-1-2-1=1$ 个金币，不足以再使用其他传送器。你共使用了两个传送器，所以答案是 $2$。 在第二个测试用例中，你可以向右移动四格并使用传送器回到 $0$ 点，然后再向右移动六格并使用第 $6$ 个传送器回到 $0$ 点。总花费为 $4+6+6+4=20$。你剩下 $12$ 个金币，但不足以到达其他传送器并使用，所以答案是 $2$。 在第三个测试用例中，你没有足够的金币使用任何传送器，所以答案是 $0$。 由 ChatGPT 4.1 翻译