P16749 [GKS 2020 #A] Workout

Tambourine 制定了一个健身计划，以便让自己变得更健康！该计划由 $N$ 个训练环节组成。在第 $i$ 个环节中，Tambourine 将锻炼 $M_i$ 分钟。她在每个环节中的锻炼分钟数是**严格递增**的。 健身计划的**难度**定义为任意两个连续训练环节之间分钟数的最大差值。 为了降低计划难度，Tambourine 决定在她的健身计划中最多添加 $K$ 个额外的训练环节。她可以将这些环节添加到计划的任意位置，并在每个额外环节中锻炼任意正整数分钟。添加额外环节后，每个环节的锻炼分钟数仍然必须严格递增。请问可能的最小难度是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$。第二行包含 $N$ 个整数，其中第 $i$ 个整数为 $M_i$，表示她在第 $i$ 个环节中锻炼的分钟数。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在最多添加 $K$ 个额外训练环节后可能的最小难度。

在样例 #1 中：Tambourine 最多可以添加一个环节。添加的环节用粗体标出：100 **150** 200 230。此时难度为 $50$。 ### 限制条件 $1 \le T \le 100$。 最多有 $10$ 个测试用例满足 $2 \le N \le 10^5$。 对于所有其他测试用例，$2 \le N \le 300$。 $1 \le M_i \le 10^9$。 对于所有 $i$，$M_i < M_{i+1}$。 **测试集 1** $K = 1$。 **测试集 2** $1 \le K \le 10^5$。 翻译由 DeepSeek V4 Pro 完成