题目描述

Aki 将在一场很长的战斗中按时刻发动共 n 次攻击。第 i 次攻击发生在时刻 a_i 的开始，且满足 a₁<a₂<…<a_n。

每次攻击本身不直接造成伤害，而是会让目标进入持续 k 秒的中毒状态：从该次攻击发生的这一秒开始，接下来的 k 秒中每秒造成 1 点伤害。

如果目标在中毒尚未结束时又被攻击，那么旧中毒会立刻被新中毒覆盖，新的持续时间重新开始计算。

已知目标生命值为 h。你需要求出最小的正整数 k，使得整场战斗中总伤害至少为 h。

输入格式

第一行一个整数 t 表示测试组数，满足 1≤ t≤ 1000。

每组测试数据包含两行。

第一行两个整数 n,h，满足 1≤ n≤ 100，1≤ h≤ 10¹⁸。

第二行 n 个整数 a₁,a₂,…,a_n，满足 1≤ a_i≤ 10⁹，且严格递增。

输出格式

对于每组测试数据，输出一个整数，表示满足要求的最小 k。

4
2 5
1 5
3 10
2 4 10
5 3
1 2 4 5 7
4 1000
3 25 64 1337

3
4
1
470

Hint

样例解释：

• 第 1 组中，当 k=3 时：

  • 时刻 1 的攻击贡献时段 [1,3]；
  • 时刻 5 的攻击贡献时段 [5,7]。

  总伤害为 3+3=6，已经不少于 5。而 k=2 时总伤害仅为 4，所以答案是 3。

• 第 2 组中，当 k=4 时，三次攻击分别覆盖：

  • [2,5]
  • [4,7]（覆盖前一次剩余部分）
  • [10,13]

  实际总伤害为

min(4,4-2)+min(4,10-4)+4=2+4+4=10,

恰好达到 h=10。

• 第 3 组中，h=3，只要 k=1 即可，每次攻击都会立刻造成 1 点伤害，总伤害至少为 3。