题目描述

你喜欢鱼，所以决定建造一个水族箱。你有一块由 $n$ 列珊瑚石组成的珊瑚，第 $i$ 列的高度为 $a_i$ 单位。接下来，你将围绕珊瑚建造一个水族箱，步骤如下：

1. 选择一个整数 $h \ge 1$ 作为水族箱的高度。在水族箱两侧建造高度为 $h$ 的墙壁。
2. 然后，向水族箱中注水，使得每一列的水面高度都达到 $h$。
   • 如果珊瑚石本身的高度 $a_i$ 已经大于或等于 $h$，则该列不添加任何水。
   • 如果珊瑚石的高度 $a_i$ 小于 $h$，则该列需要添加 $h - a_i$ 单位的水。

示例： 对于高度数组 $a = [3, 1, 2, 4, 6, 2, 5]$ 且设定高度 $h = 4$，你总共需要使用的水量 $w = 8$ 单位。

你最多可以使用 $x$ 单位的水来填充水族箱，你希望建造尽可能大的水族箱。你能选择的最大高度 $h$ 是多少？

输入格式

• 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。
• 每个测试用例的第一行包含两个正整数 $n$ 和 $x$ ($1 \le n \le 2 \cdot 10^5; 1 \le x \le 10^9$) —— 珊瑚石的列数以及你最多能使用的水量。
• 每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_i$ ($1 \le a_i \le 10^9$) —— 各列珊瑚石的高度。
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个正整数 $h$ ($h \ge 1$) —— 水族箱能具有的最大高度，使得填充水族箱所需的水量不超过 $x$ 单位。

可以证明，在给定的约束下，这样的 $h$ 总是存在的。

样例输入输出

输入：

5
7 9
3 1 2 4 6 2 5
3 10
1 1 1
4 1
1 4 3 4
6 1984
2 6 5 9 1 8
1 1000000000
1

输出：

4
4
2
335
1000000001