310590: CF1856C. To Become Max

C. To Become Maxtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

4
7
179
5
7
6

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

题目大意：
给定一个长度为n的整数数组a。每次操作你可以选择一个索引i，满足1≤i≤n−1且ai≤ai+1，然后将ai增加1。问最多进行k次操作后，数组a中的最大值最大可以为多少。

输入数据格式：
第一行包含一个整数t，表示测试用例的数量。每个测试用例包含两行，第一行为两个整数n和k，分别表示数组a的长度和最多进行的操作次数。第二行为n个整数，表示数组a的每个元素的值。

输出数据格式：
对于每个测试用例，输出一行，包含一个整数，表示最多进行k次操作后，数组a中的最大值最大可以为多少。

输入输出样例：
输入
```
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
```
输出
```
4
7
179
5
7
6
```

注意：
- 在第一个测试用例中，一种可能的最优操作序列是：[1,3,3]→[2,3,3]→[2,4,3]→[3,4,3]→[4,4,3]。
- 在第二个测试用例中，一种可能的最优操作序列是：[1,3,4,5,1]→[1,4,4,5,1]→[1,5,4,5,1]→[1,5,5,5,1]→[1,5,6,5,1]→[1,6,6,5,1]→[1,7,6,5,1]。题目大意： 给定一个长度为n的整数数组a。每次操作你可以选择一个索引i，满足1≤i≤n−1且ai≤ai+1，然后将ai增加1。问最多进行k次操作后，数组a中的最大值最大可以为多少。 输入数据格式： 第一行包含一个整数t，表示测试用例的数量。每个测试用例包含两行，第一行为两个整数n和k，分别表示数组a的长度和最多进行的操作次数。第二行为n个整数，表示数组a的每个元素的值。 输出数据格式： 对于每个测试用例，输出一行，包含一个整数，表示最多进行k次操作后，数组a中的最大值最大可以为多少。 输入输出样例： 输入 ``` 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 ``` 输出 ``` 4 7 179 5 7 6 ``` 注意： - 在第一个测试用例中，一种可能的最优操作序列是：[1,3,3]→[2,3,3]→[2,4,3]→[3,4,3]→[4,4,3]。 - 在第二个测试用例中，一种可能的最优操作序列是：[1,3,4,5,1]→[1,4,4,5,1]→[1,5,4,5,1]→[1,5,5,5,1]→[1,5,6,5,1]→[1,6,6,5,1]→[1,7,6,5,1]。