该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：max.in

输出：max.out

题目描述

给定一个长度为 $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)$ 的最大可能值。

输入格式

每个测试点包含多组测试数据。输入的第一行包含一个整数 $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$。

输出格式

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

输入输出样例

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

说明/提示

在样例的第一个测试用例中，一种可能的最优操作序列为：$[\textcolor{red}{1}, 3, 3] \rightarrow [2, \textcolor{red}{3}, 3] \rightarrow [\textcolor{red}{2}, 4, 3] \rightarrow [\textcolor{red}{3}, 4, 3] \rightarrow [4, 4, 3]$。

在样例的第二个测试用例中，一种可能的最优操作序列为：$[1, \textcolor{red}{3}, 4, 5, 1] \rightarrow [1, \textcolor{red}{4}, 4, 5, 1] \rightarrow [1, 5, \textcolor{red}{4}, 5, 1] \rightarrow [1, 5, \textcolor{red}{5}, 5, 1] \rightarrow [1, \textcolor{red}{5}, 6, 5, 1] \rightarrow [1, \textcolor{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$。