题目描述

一条笔直的长廊上从左到右依次有 $n$ 座传送阵，第 $i$ 座位于坐标 $i$； 坐标 $0$ 与坐标 $n+1$ 处各有一道门，可以从任意一端进出长廊。

小爱一开始站在坐标 $0$ 处，身上的金币数为 $c$。他可以做三类动作，每次移动一单位距离 花费 $1$ 枚金币：

• 从当前位置向右移动一个单位；
• 从当前位置向左移动一个单位；
• 使用当前位置的传送阵：花费 $a_i$ 枚金币，然后被立即传送到坐标 $0$ 或坐标 $n+1$ （送到哪一端由小爱自己选择）。

每座传送阵在整场练习中最多只能使用一次。小爱希望用身上的金币使用尽可能多的传送阵。

请你对 $T$ 组给定的场地分别回答：在给定金币数下最多能使用多少座传送阵。

输入格式

从文件 warp.in 读入数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组数据，每组数据的格式为：

第一行包含两个整数 $n$ 与 $c$，分别表示传送阵数量与小爱携带的金币数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示使用第 $i$ 座传送阵所需的花费。

输出格式

输出到文件 warp.out。

对于每组数据，输出一行一个整数，表示小爱最多能使用的传送阵数量。

样例

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$（花 $1$ 枚），使用第 $1$ 座传送阵（花 $1$ 枚）并选择 传到坐标 $6$；再向左走到坐标 $5$（花 $1$ 枚），使用第 $5$ 座传送阵（花 $1$ 枚）。 一共花了 $4$ 枚金币，剩 $2$ 枚，所以这组输出对应的方案是合法的。

第五组数据：一种可行方案是依次使用第 $1, 5, 3$ 座传送阵。小爱先向右走到坐标 $1$ 使用第 $1$ 座（花 $1 + 2 = 3$ 枚）并选择传到坐标 $6$；再向左走到坐标 $5$ 使用第 $5$ 座 （花 $1 + 1 = 2$ 枚）并选择传到坐标 $0$；最后向右走到坐标 $3$ 使用第 $3$ 座 （花 $3 + 1 = 4$ 枚）。总花费 $3 + 2 + 4 = 9$ 枚金币，恰好用完，答案是 $3$。

样例 2&3

见下发文件

数据范围

对于所有测试数据，保证：

• $1 \le T \le 1000$；
• $1 \le n \le 2 \times 10^5$，$1 \le c \le 10^9$；
• $1 \le a_i \le 10^9$；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。