To Become Max
Contest: Codeforces Round 890 (Div. 2) supported by Constructor Institute
Difficulty rating: 1600
Tags: binary search, brute force, data structures, dp

You are given an array of integers $$$a$$$ of length $$$n$$$.

In one operation you:

- Choose an index $$$i$$$ such that $$$1 \le i \le n - 1$$$ and $$$a_i \le a_{i + 1}$$$.
- Increase $$$a_i$$$ by $$$1$$$.

Find the maximum possible value of $$$\max(a_1, a_2, \ldots a_n)$$$ that you can get after performing this operation at most $$$k$$$ times.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 10^{8}$$$) — the length of the array $$$a$$$ and the maximum number of operations that can be performed.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{8}$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case output a single integer — the maximum possible maximum of the array after performing at most $$$k$$$ operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one possible optimal sequence of operations is: $$$[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$$$.

In the second test case, one possible optimal sequence of operations is: $$$[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$$$.

Example input:
6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5

Example output:
4
7
179
5
7
6

Editorial:
We will do binary search on the answer. The lower bound can be set to $$$0$$$, while $$$\max(a_1, \ldots a_n) + k$$$ is clearly enough for the upper bound.
Let $$$b$$$ be some resulting array after performing at most $$$k$$$ operations.
Suppose for some $$$x$$$ we want to check if we can get $$$\max(b_1, \ldots b_n) \ge x$$$ in at most $$$k$$$ operations. That is, there must exist some index $$$i$$$ such that $$$b_i \ge x$$$. So, let's iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and check if it possible to have $$$b_i \ge x$$$ in at most $$$k$$$ operations.
Let $$$f(i, y)$$$ be the minimum number of operations needed to make $$$b_i \ge y$$$. Then:
• $$$f(i, y) = 0$$$ for all $$$y \le a_i$$$,
• $$$f(i, y) = y - a_i + f(i + 1, y - 1)$$$ for all $$$1 \le i < n$$$ and $$$y > a_i$$$,
• $$$f(i, y) = +\infty$$$ for $$$i = n$$$ and all $$$y > a_i$$$.
It is easy to see that calculating $$$f(i, x)$$$ takes $$$\mathcal{O}(n)$$$ time for one call in the worst case.
Thus, our check consists of comparing $$$f(i, x)$$$ and $$$k$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$. If at least one of the values is $$$\le k$$$, it is possible to have some $$$b_i \ge x$$$ in at most $$$k$$$ operations and we increase the lower bound in the binary search after updating the current answer. Otherwise, it is impossible and we decrease the upper bound.
Complexity: $$$\mathcal{O}(n^2 \cdot \log A)$$$, where A is the maximum possible value of $$$a_i$$$ and $$$k$$$.
Notes:
• You can get a $$$\mathcal{O}(n^2 \cdot \log n)$$$ solution by setting the lower bound in the binary search to $$$\max(a_1, \ldots, a_n)$$$ and the upper bound to $$$\max(a_1, \ldots, a_n) + n$$$.
• There exists a $$$\mathcal{O}(n^2)$$$ dp solution that relies on the fact that the answer lies in the range $$$[ \max(a_1, \ldots, a_n); \max(a_1, \ldots, a_n) + n ]$$$