题目描述

在一个魔法世界中，有 n 座魔法塔排成一排，每座魔法塔的高度为 a[i]。魔法师可以使用魔法卷轴来提升魔法塔的高度。

在一次魔法操作中，魔法师可以：

• 选择相邻的两座魔法塔 i 和 i+1，其中第 i 座塔的高度不超过第 i+1 座塔的高度（即 a[i] ≤ a[i+1]）。
• 在第一点的前提下，可以使用一个魔法卷轴，将第 i 座塔的高度提升 1 单位。
• 魔法卷轴不一定要全部使用完。
• 魔法卷轴可以对同一个塔多次使用

魔法师最多可以使用 k 个魔法卷轴。目标是让所有魔法塔中最高的那座塔的高度尽可能大。

输入

输入包含多个测试用例。输入的第一行是一个整数 t（1 ≤ t ≤ 100），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 n 和 k（2 ≤ n ≤ 1000，1 ≤ k ≤ 10^8），分别表示魔法塔的数量和最多可以使用的魔法卷轴数量。

每个测试用例的第二行包含 n 个整数 a1, a2, …, an（1 ≤ ai ≤ 10^8），表示每座魔法塔的初始高度。

保证所有测试用例的 n 的总和不超过 1000。

输出

对于每个测试用例，会得到一个结果，该结果表示在最多使用 k 个魔法卷轴后，最高的魔法塔的最大可能高度。注意每个测试结果要换行输出

示例

input

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

output

4
7
179
5
7
6

解释

在第二个测试用例中，魔法师可以按以下方式使用魔法卷轴： 初始状态：[1, 3, 4, 5, 1] 使用 1 个卷轴：[1, 4, 4, 5, 1] 使用 2 个卷轴：[1, 5, 4, 5, 1] 使用 3 个卷轴：[1, 5, 5, 5, 1] 使用 4 个卷轴：[1, 5, 6, 5, 1] 使用 5 个卷轴：[1, 6, 6, 5, 1] 使用 6 个卷轴：[1, 7, 6, 5, 1] 最终最高的魔法塔高度为 7

限制

时间限制：1s 空间限制：128 MB