题目描述

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

每次操作你可以：

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

请你求出，在最多进行 $k$ 次操作后，数组 $a$ 的最大值 $\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$ 次操作后，数组的最大值的最大可能值。

说明/提示

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

由 ChatGPT 4.1 翻译

样例

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