← 返回题目列表

Codeforces · 1856/C

C. 成为最大

中文机器翻译题面 查看原题

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

在一次操作中,您:

- 选择一个索引 $$$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$$$ 操作后数组的最大可能最大值。

示例

输入 #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

输出 #1

4
7
179
5
7
6

注意

在第一个测试用例中,一个可能的最佳操作顺序是: $$$[\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]$$$。