题目描述

小T原先给自己制定了一个锻炼计划，这个锻炼计划分为 N 个阶段，在第 i 个阶段小T需要持续锻炼 ai 分钟，并且每个阶段的锻炼时长是严格递增的。

这个锻炼计划的难度系数为任意两次连续训练之间分钟数的最大差值。

但是小T发现原先制定的锻炼计划难度系数太高了，为了降低难度，小T打算往锻炼计划中加入 K 个新的阶段，这些新的阶段可以设置任意位置任意时长，但最终形成的计划必须保持严格递增。

请问小T最低能将难度系数降到多少？

输入格式

第一行一个整数 T，表示数据组数。每组数据格式如下：

第一行两个整数 N,K，分别表示原锻炼计划的阶段数和可新增的阶段数；

第二行 N 个整数，第 i 个数即为原锻炼计划中第 i 个阶段的时长 ai。

输出格式

T 行，每行对应一组数据的答案

测试样例

输入样例 #1

2

3 1

100 200 230

5 6

9 10 20 26 30

输出样例 #1

50

3

样例解释

样例一说明

第一组数据中，允许加入 1 个新的阶段。

在 100 分钟和 200 分钟之间加入一个 150 分钟的阶段能使难度系数降至 50。易知该方案是最佳方案。

第二组数据中，允许加入 6 个新的阶段。

最低能将难度系数降至 3。具体操作为： 9,10,12,14,16,18,20,23,26,29,30，其中 12,14,16,18,23,29 为加入的 6 个新阶段。

数据范围 对于 25% 的数据，K=1。

对于 100% 的数据，1≤T≤100,2≤N≤105,1≤K≤105,1≤ai≤109，给定的 ai 序列严格递增。