CF1873E.Building an Aquarium

You love fish, that's why you have decided to build an aquarium. You have a piece of coral made of $n$ columns, the $i$-th of which is $a_i$ units tall. Afterwards, you will build a tank around the coral as follows:

• Pick an integer $h \geq 1$ — the height of the tank. Build walls of height $h$ on either side of the tank.
• Then, fill the tank up with water so that the height of each column is $h$, unless the coral is taller than $h$; then no water should be added to this column.

For example, with $a=[3,1,2,4,6,2,5]$ and a height of $h=4$, you will end up using a total of $w=8$ units of water, as shown.

You can use at most $x$ units of water to fill up the tank, but you want to build the biggest tank possible. What is the largest value of $h$ you can select?

你非常喜欢鱼，因此决定建造一个水族箱。你有一块由 $n$ 列珊瑚组成的珊瑚礁，其中第 $i$ 列的高度为 $a_i$ 个单位。之后，你将围绕这块珊瑚建造一个水箱，具体步骤如下：

• 选择一个整数 $h \geq 1$ —— 即水箱的高度。在水箱左右两侧各建造高度为 $h$ 的墙壁。
• 然后向水箱中注水，使得每列的总高度（珊瑚高度加水高度）达到 $h$；但如果某列珊瑚本身已高于 $h$，则该列不加水。

例如，当 $a=[3,1,2,4,6,2,5]$ 且水箱高度 $h=4$ 时，总共需要 $w=8$ 单位的水，如下图所示。

你最多只能使用 $x$ 单位的水来注满水箱，但你希望建造尽可能大的水箱。你能选择的最大 $h$ 值是多少？

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two positive integers $n$ and $x$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq x \leq 10^9$) — the number of columns of the coral and the maximum amount of water you can use.

The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^9$) — the heights of the coral.

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $x$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq x \leq 10^9$）—— 珊瑚的列数以及你最多可使用的水量。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^9$）—— 各列珊瑚的高度。

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

For each test case, output a single positive integer $h$ ($h \geq 1$) — the maximum height the tank can have, so you need at most $x$ units of water to fill up the tank.

We have a proof that under these constraints, such a value of $h$ always exists.

对于每个测试用例，输出一个正整数 $h$（$h \geq 1$）——即水箱可能达到的最大高度，使得填满该水箱所需水量至多为 $x$ 个单位。

在本题约束条件下，可以证明这样的 $h$ 值一定存在。

The first test case is pictured in the statement. With $h=4$ we need $8$ units of water, but if $h$ is increased to $5$ we need $13$ units of water, which is more than $x=9$. So $h=4$ is optimal.

In the second test case, we can pick $h=4$ and add $3$ units to each column, using a total of $9$ units of water. It can be shown that this is optimal.

In the third test case, we can pick $h=2$ and use all of our water, so it is optimal.

第一个测试用例如题面图示所示。当 $h=4$ 时，我们需要 $8$ 单位的水；但若将 $h$ 增加至 $5$，则需要 $13$ 单位的水，超过了 $x=9$。因此 $h=4$ 是最优的。

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

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