题目描述

考虑数字线上的点 $0,1,…,n+1$。在点 $1,2,…,n$ 中的每个点上都有一个隐形传态器。在点 $i$，可以执行以下操作：

• 向左移动一个单位：它需要 $1$ 个硬币。
• 向右移动一个单位：它需要 $1$ 个硬币。
• 在 $i$ 点使用传送机：它需要 $a_i$ 硬币，然后你传送到 0 点或者 n+1 点。每个传送机都只能使用一次。

你有 $c$ 个硬币，从 0 点开始。你能使用的传送机最多有多少？

输入格式

输入由多个测试用例组成。第一行包含整数 $t(1≤t≤1000)$ 代表测试用例数。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $n,c(1≤n≤2×10^5;1≤c≤10^9)$，分别是数组的长度和硬币的数量。

以下行包含 $n$ 个空间分隔的整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ 代表使用传送机的成本。

保证所有测试用例的 $n$ 之和不超过 $2×10^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$ 个单位，使用索引 1 处的传送机并传送到 0 点，向右移动 $2$ 个单位并使用索引 2 处的传送器。你只剩下 $6−1−1−2−1=1$ 个硬币，你没有足够的硬币来使用另一个传送机，所以答案是 $2$ 个。

在第二个测试案例中，你向右移动 $4$ 个单位，使用传送机到达 n+1，然后向左移动 $3$ 个单位，使用传送机达到 n+1，最后向左移动 $4$ 个单位，使用传送机。总成本将是 $4+6+3+4+4+9=30$，你使用了 $3$ 次传送。

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