题目描述

江月诗 在玩一款叫做 Qenerals 的游戏。

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

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

• 在第 $i$ 秒开始时，每个 江月诗 所占领的堡垒都会为 江月诗 生产 $1$ 个士兵，即 $x \gets x + y$。

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

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

输入格式

本题包含多组测试数据。

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

对于每组测试数据：

• 第一行包含两个正整数 $n, m\ (1 \le n \le 5 \cdot 10^5,\ 1 \le m \le 10^9)$。

• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)$。

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

输出格式

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

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

4
13
12

说明/提示

• 对于第 1 组测试数据：

  • 在第 $1$ 秒开始时，江月诗 占领的堡垒数 $y = 1$，因此 江月诗 拥有的士兵数量 $x$ 由 $0$ 变为了 $1$。

  • 在第 $1$ 秒结束时，江月诗 可以选择占领第 $2$ 个堡垒，因此 江月诗 占领的堡垒数 $y$ 由 $1$ 变为了 $2$，拥有的士兵数量 $x$ 由 $1$ 变为了 $0$。

  • 在第 $2$ 秒开始时，江月诗 占领的堡垒数 $y = 2$，因此 江月诗 拥有的士兵数量 $x$ 由 $0$ 变为了 $2$。

  • 在第 $2$ 秒结束时，江月诗 可以选择不进行任何操作。

  • 在第 $3$ 秒开始时，江月诗 占领的堡垒数 $y = 2$，因此 江月诗 拥有的士兵数量 $x$ 由 $2$ 变为了 $4$。

  • 在第 $3$ 秒结束时，江月诗 可以选择不进行任何操作。

  • 在游戏结束后，江月诗 拥有的士兵数量 $x$ 达到了 $4$。可以证明，在游戏结束后 江月诗 最多能拥有的士兵数量即为 $4$。

• 对于第 2 组测试数据：

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

• 对于第 3 组测试数据：

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