题目描述

你喜欢鱼，因此决定建造一个水箱。你有一个由 $n$ 列组成的珊瑚，其中第 $i$ 列的高度是 $a_i$。之后，你将按照以下方式在珊瑚周围建造一个水箱：

选择一个整数 $h(h≥1)$ — 水箱的高度。在水箱的两侧建造高度为 $h$ 的墙壁。

然后，用水填满水箱，以便每列的高度都是 $h$，除非珊瑚比 $h$ 更高（在这种情况下，不应向此列添加水）。

例如，对于 $a=[3,1,2,4,6,2,5]$ 和 $h=4$，你将使用总共 $w=8$ 个单位的水，如图所示。

你最多可以使用 $x$ 个单位的水来填满水箱，但你想建造尽可能高的水箱。问，你可以选择的最大 $h$ 是多少？

输入格式

第一行包含一个整数 $t(1≤t≤10^4)$ — 测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $x(1≤n≤2×10^5; 1≤x≤10^9)$ — 珊瑚的列数和最大使用水的量。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_i(1≤a_i≤10^9)$ — 珊瑚的高度。

所有测试用例中 $n$ 的总和不超过 $2×10^5$。

输出格式

对于每个测试用例，输出一个单独的正整数 $h(h≥1)$ — 水箱的最大高度，填满该水箱所需的水不超过 $x$ 个单位。

测试样例

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

样例说明

第一个测试用例在陈述中已经展示了。当 $h=4$ 时，我们需要 8 个单位的水，但如果将 $h$ 增加到 5，我们需要 13 个单位的水，这超过了 $x=9$。因此，$h=4$ 是最优的。

在第二个测试用例中，我们可以选择 $h=4$ 并向每列添加 3 个单位，总共使用了 9 个单位的水。可以证明这是最优的。

在第三个测试用例中，我们可以选择 $h=2$ 并使用所有的水，因此这是最优的。