Building an Aquarium
Description
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.
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$.
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.
Input
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$.
Output
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.
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
Note
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.