Monocarp 正在玩另一个电脑游戏。在这个游戏中,他的角色必须杀死一条龙。与龙的战斗持续$$$100^{500}$$$秒,在此期间Monocarp用有毒的匕首攻击龙。第 $$$i$$$ 次攻击在战斗开始后第 $$$a_i$$$ 秒开始时执行。匕首本身不会造成伤害,但它会对龙施加毒害效果,在接下来的$$$k$$$秒内造成$$$1$$$伤害(从龙被匕首刺伤的同一秒开始)。然而,如果龙已经中毒,那么匕首会更新毒性效果(即取消当前的毒性效果并应用新的毒性效果)。
例如,假设$$$k = 4$$$,并且 Monocarp 在 $$$2$$$、$$$4$$$ 和 $$$10$$$ 秒内刺伤了龙。然后在第 $$$2$$$-nd 秒开始时应用中毒效果,并在 $$$2$$$-nd 和 $$$3$$$-rd 秒内造成 $$$1$$$ 伤害;然后,在第 $$$4$$$ 秒开始时,重新应用中毒效果,因此它在 $$$4$$$、$$$5$$$、$$$6$$$ 和 $$$7$$$ 秒内精确造成 $$$1$$$ 伤害;然后,在第 $$$10$$$ 秒内,再次应用中毒效果,并在 $$$10$$$、$$$11$$$、$$$12$$$ 和 $$$13$$$ 秒内造成 $$$1$$$ 伤害。龙总共受到 $$$10$$$ 伤害。
Monocarp 知道龙有 $$$h$$$ 生命值,如果他在战斗中对龙造成至少 $$$h$$$ 伤害 — 他就会杀死龙。 Monocarp 尚未决定他将在战斗中使用的毒药的强度,因此他想要找到 $$$k$$$(毒药效果持续的秒数)的最小可能值,该值足以对龙造成至少 $$$h$$$ 伤害。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$h$$$ ($$$1 \le n \le 100; 1 \le h \le 10^{18}$$$) — Monocarp 的攻击次数和需要造成的伤害量。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9; a_i < a_{i + 1}$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 次攻击发生时的第二个攻击执行。
输出
对于每个测试用例,打印一个整数 - 参数 $$$k$$$ 的最小值,这样 Monocarp 将对龙造成至少 $$$h$$$ 伤害。
示例
输入 #1
4 2 5 1 5 3 10 2 4 10 5 3 1 2 4 5 7 4 1000 3 25 64 1337
输出 #1
3 4 1 470
注意
在第一个示例中,对于 $$$k=3$$$,伤害以秒 $$$[1, 2, 3, 5, 6, 7]$$$ 为单位造成。
在第二个示例中,对于 $$$k=4$$$,伤害以秒 $$$[2, 3, 4, 5, 6, 7, 10, 11, 12, 13]$$$ 为单位造成。
在第三个示例中,对于 $$$k=1$$$,伤害以秒 $$$[1, 2, 4, 5, 7]$$$ 为单位造成。