CF1856C.To Become Max

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.

给你一个长度为 $n$ 的整数数组 $a$。

在一次操作中，你可以：

• 选择一个下标 $i$，满足 $1 \le i \le n - 1$ 且 $a_i \le a_{i + 1}$；
• 将 $a_i$ 的值增加 $1$。

求在最多执行 $k$ 次该操作后，$\max(a_1, a_2, \ldots, a_n)$ 的最大可能值。

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$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 1000$，$1 \le k \le 10^{8}$），分别表示数组 $a$ 的长度以及最多可执行的操作次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^{8}$），表示数组 $a$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $1000$。

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

对于每个测试用例，输出一个整数——在最多执行 $k$ 次操作后，数组可能达到的最大值。

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]$.

在第一个测试用例中，一种可能的最优操作序列为：$[\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]$。

在第二个测试用例中，一种可能的最优操作序列为：$[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]$。