You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Bob想建造一个水箱。水箱底部有一块珊瑚，由$n$列组成，其中第$i$列的高度为$a_i$。他将按照以下方式依靠珊瑚建造一个水箱：

• 选择一个整数$h\geq1$，作为水箱的高度。在水箱的两侧建造高度为$h$的墙壁。
• 将水箱填满水，使得每一列的高度都为$h$；如果珊瑚高度超过$h$，则该列不需要添水。

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

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

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含两个正整数$n$和$x$，表示珊瑚的列数和Bob可以使用的最大水量。

每个测试用例的第二行包含$n$个以空格分隔的整数$a_i$，表示珊瑚的高度。

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

输出格式

对于每个测试用例，输出一个正整数$h(h\geq 1)$，表示水箱的最大高度，使得Bob需要至多$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$时，$Bob$需要$8$个单位的水，但是如果将$h$增加到$5$，Bob将需要$13$个单位的水，这超过了$x=9$。因此，$h=4$是最优解。

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

对于第三个测试用例，Bob可以选择$h=2$，使用所有的水，因此这是最优解。

【数据范围】

对于所有数据，保证：$1\leq t \leq 10^4,1\leq n\leq2\cdot10^5,1\leq x\leq 10^9,1\leq a_i\leq 10^9$。所有测试用例中$n$的总和不超过$2\cdot10^5$。