题解思路

关键观察

只能“加”，不能“减”。因此想要让相邻差变小，只能把较小的那个数往上抬。

把答案（相邻差最大值）记为 X，考虑判定问题：

是否能用不超过 k 次加一操作，使得最终数组 b 满足

题目内容

小红有一个长度为 $n$ 的数组 $a$ 。

小红可以对数组执行最多 $k$ 次如下操作：

指定数组中的某个元素 $a_i(1≤i≤n)$ ，令 $a_i=a_i+1$ 。对于同一个位置的元素可以多次进行操作。

小红想要最小化数组中相邻元素差的绝对值的最大值，请你帮助他计算。

输入描述

输入包括多组测试数据。

输入第一行有一个正整数 $T(1≤T≤100)$ ，表示测试数据的组数。

对于每组测试数据：

第一行有两个正整数 $n(2≤n≤10^5)$ ，$k(0≤k≤10^9)$ ，分别表示数组的长度、操作最多可以执行多少次。

接下来的一行有 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ ，表示题目给定的数组。

输出描述

对于每组测试数据，输出一个正整数，表示经过操作后数组中相邻元素差的绝对值的最大值最小是多少。

样例1

输入

1
5 3
3 1 5 4 1

输出

2

说明

其中一种可行的操作为：对第二个元素执行两次操作，对第五个元素执行一次操作，得到新数组 $[3$ $3$ $5$ $4$ $2]$，相邻元素差的绝对值的最大值为 $2$ ，此时最小。