题面描述

给定两个正整数 $n$ 和 $k$，以及一个长度为 $n$ 的序列 $a$，你可以进行不超过 $k$ 次如下操作（以下两个步骤合称一次操作）：

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

求操作完成后，$\max \limits_{i = 1} ^ {n} a_i$ 的最大可以是多少。

多测，共 $t$ 组数据。

对于所有数据，保证 $1 \le t \le 100$，$1 \le n, \sum n \le 1000$，$1 \le k, a_i \le 10 ^ 8$。

输入格式

第一行正整数t代表多组数据的组数。($1\le t\le 100)$

每组数据第一行包含两个正整数n和k $(2\le n \le 1000 , 1 \le k \le 10^8)$ 分别表示数组的长度 和 最多的操作次数。

第二行包含 $n$ 个正整数$a_1,a_2,\ldots,a_n$ ( $1 \le a_i \le 10^{8}$ )

保证对于所有组数据，$n$ 的总和 不超过 1000

输出格式

对于每组数据，输出一个正整数，代表最多经过k次操作之后，数组中最大的元素。

样例 #1

样例输入 #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] $ .