Codeforces Round 898 (Div. 4) |
---|
Finished |
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:
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.
57 93 1 2 4 6 2 53 101 1 14 11 4 3 46 19842 6 5 9 1 81 10000000001
4 4 2 335 1000000001
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.
Name |
---|