题目描述

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

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

输出格式

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

样例

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
2
0
1
2
2
1
1
1
2

样例说明

在第一个测试用例中，你可以向右移动一格，使用第 $1$ 个传送器并传送回 $0$ 点，再向右移动两格，使用第 $2$ 个传送器。你剩下 $6-1-1-2-1=1$ 个金币，不足以再使用其他传送器。你共使用了两个传送器，所以答案是 $2$。

在第二个测试用例中，你可以向右移动四格并使用传送器回到 $0$ 点，然后再向右移动六格并使用第 $6$ 个传送器回到 $0$ 点。总花费为 $4+6+6+4=20$。你剩下 $12$ 个金币，但不足以到达其他传送器并使用，所以答案是 $2$。

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

由 ChatGPT 4.1 翻译

来源

Codeforces 1791G1，英文题名 Teleporters (Easy Version)。