题目描述

Yuki 在玩一款叫做 Qenerals 的游戏。

第 $0$ 秒时，Yuki 拥有的士兵数量 $x = 0$，占领的堡垒数量 $y = 1$。地图上还有 $n$ 个未被占领的堡垒，第 $i$ 个堡垒的参数为 $a_i$。

游戏一共会进行 $m$ 秒。对于每个不大于 $m$ 的正整数 $i$：

• 在第 $i$ 秒开始时，每个 Yuki 所占领的堡垒都会为 Yuki 生产 $1$ 个士兵，即 $x \leftarrow x + y$。
• 在第 $i$ 秒结束时，Yuki 可以进行任意次操作（可以为 $0$ 次）；每次操作，Yuki 需要选择一个未被占领的堡垒 $j$ 满足 $a_j \le x$，接着消耗 $a_j$ 个士兵并占领第 $j$ 个堡垒，即 $x \leftarrow x - a_j$ 且 $y \leftarrow y + 1$。

你需要帮助 Yuki 求出，在游戏结束后，她最多能拥有多少个士兵。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个正整数 $n, m$ $(1 \le n \le 5\cdot10^5,\ 1 \le m \le 10^{9})$。
• 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$ $(1 \le a_i \le 10^9)$。

保证所有测试数据中 $n$ 的总和不超过 $5\cdot10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示在游戏结束后 Yuki 最多能拥有的士兵数量。

3
2 3
2 1
3 6
1 1 3
3 5
1 1 1

4
13
12

提示

对于第 $1$ 组测试数据：

• 在第 $1$ 秒开始时，Yuki 占领的堡垒数 $y = 1$，因此 Yuki 拥有的士兵数量 $x$ 由 $0$ 变为了 $1$。
• 在第 $1$ 秒结束时，Yuki 可以选择占领第 $2$ 个堡垒，因此 Yuki 占领的堡垒数 $y$ 由 $1$ 变为了 $2$，拥有的士兵数量 $x$ 由 $1$ 变为了 $0$。
• 在第 $2$ 秒开始时，Yuki 占领的堡垒数 $y = 2$，因此 Yuki 拥有的士兵数量 $x$ 由 $0$ 变为了 $2$。
• 在第 $2$ 秒结束时，Yuki 可以选择不进行任何操作。
• 在第 $3$ 秒开始时，Yuki 占领的堡垒数 $y = 2$，因此 Yuki 拥有的士兵数量 $x$ 由 $2$ 变为了 $4$。
• 在第 $3$ 秒结束时，Yuki 可以选择不进行任何操作。
• 在游戏结束后，Yuki 拥有的士兵数量 $x$ 达到了 $4$。可以证明，在游戏结束后 Yuki 最多能拥有的士兵数量即为 $4$。

对于第 $2$ 组测试数据：

• Yuki 可以在第 $1,2,3$ 秒时分别占领第 $1,2,3$ 个堡垒，使 Yuki 在游戏结束后拥有的士兵数量达到 $13$。

对于第 $3$ 组测试数据：

• Yuki 可以在第 $1$ 秒时占领第 $1$ 个堡垒，并在第 $2$ 秒时占领第 $2$ 个堡垒和第 $3$ 个堡垒，使 Yuki 在游戏结束后拥有的士兵数量达到 $12$。