CF1613C Poisoned Dagger

Monocarp 正在玩另一款电脑游戏。在这款游戏中，他的角色需要击杀一条龙。与龙的战斗持续 $100^{500}$ 秒，在此期间，Monocarp 会用一把涂有毒药的匕首攻击巨龙。第 $i$ 次攻击发生在战斗开始后的第 $a_i$ 秒的开始时刻。匕首本身不会造成伤害，但会对巨龙施加中毒效果，使其在接下来的 $k$ 秒内（从被刺中的那一秒开始）每秒受到 $1$ 点伤害。然而，如果巨龙已经中毒，则匕首会刷新中毒效果（即取消当前的中毒效果并重新施加新的中毒效果）。 例如，假设 $k=4$，Monocarp 在第 $2$、$4$ 和 $10$ 秒刺中了巨龙。那么中毒效果会在第 $2$ 秒开始生效，并在第 $2$ 和 $3$ 秒各造成 $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, \ldots, a_n$（$1 \le a_i \le 10^9; a_i < a_{i+1}$），其中 $a_i$ 表示第 $i$ 次攻击发生的秒数。

对于每个测试用例，输出一个整数，表示使 Monocarp 至少能对巨龙造成 $h$ 点伤害所需的最小 $k$ 值。

在第一个样例中，当 $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]$ 秒。 由 ChatGPT 4.1 翻译