给定一个整数数组 $$$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]$$$。