题目描述

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
3 1
100 200 230

Case #1: 50

3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

Case #1: 2
Case #2: 3
Case #3: 1

提示

在样例 #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 完成