| 玩具熊的五夜后宫 1 首歌曲 — 活墓碑 |
设 $$$n, m, \ell$$$ 为正整数。你做出了一个不幸的决定,在 Freddy Fazbear's Pizzeria 担任夜间警卫,那里有 $$$m$$$ 的电子动画,编号为 $$$1、\ldots、m$$$ 等着来吓唬你。
夜晚由 $$$\ell$$$ 秒组成,编号为 $$$1、\ldots、\ell$$$。 $$$m$$$ 电子动画中的第 $$$j$$$ 有一个 危险等级 $$$d_j$$$,最初$$$d_1 = \ldots = d_m = 0$$$。每一秒,恰好有一个电子动画设备的危险等级会增加 $$$1$$$,并且整个晚上,您都可以观察当前时间 $$$d_j$$$ 的所有值。例如,如果 $$$m = 2$$$,则 $$$5$$$ 秒后危险级别的一个可能列表为 $$$[d_1, d_2] = [2, 3]$$$。
然而,你并非毫无防备。在每个 $$$n$$$ 固定时间 $$$a_i$$$ ($$$1 \leq a_1 \lt \ldots \lt a_n \leq \ell$$$),您可以将手电筒照射到您选择的一个电子动画 $$$j_i$$$ 上。这会在第 $$$a_i$$$ 秒之后立即发生,并将其危险级别设置回零,即 $$$d_{j_i} := 0$$$。请注意,此选择是针对每个手电筒使用 $$$a_i$$$ 独立做出的。继续之前的示例,如果 $$$a_1 = 5$$$ 并且您选择当时闪烁第二个电子动画,则 $$$5$$$ 秒后的危险级别将为 $$$[d_1, d_2] = [2, 0]$$$。
让 总体危险 是所有电子动画中的最大危险,即 $$$\max_{1 \leq j \leq m} d_j$$$。如果晚上结束时($$$\ell$$$ 秒后)的总体危险大于 $$$x$$$,你就会失败。找到 $$$x$$$ 的最小值,这样无论电子动画的动作如何,您都可以保证 总体危险 将小于或等于 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$\ell$$$ ($$$1 \leq n, m, \ell \leq 2 \cdot 10^5, n \leq \ell, 1 \leq m \cdot \ell \leq 2 \cdot 10^5$$$) — 手电筒数量分别是动作、电子动画和夜晚的长度。
下一行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \leq a_1 \lt \ldots \lt a_n \leq \ell$$$) - 您打开手电筒的时间。
保证所有测试用例的 $$$m \cdot \ell$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 最小 $$$x$$$,这样您就可以保证最终的危险级别最多为 $$$x$$$。
示例
输入复制
71 2 10105 1 321 4 9 16 252 3 4013 372 2 76 78 5 603 17 20 28 36 44 45 506 7 19876 7 66 77 666 7771 1 11
输出复制
571911914770
注意
在第一个测试用例中,有 $$$2$$$ 电子动画和 $$$10$$$ 的夜间长度,并且你会在第 $$$10$$$ 秒后闪烁。我们将证明 $$$x = 5$$$ 总是可能的。 $$$10$$$ 秒后,请注意,一个电子动画必须至少有 $$$5$$$ 危险,而另一个电子动画必须最多有 $$$5$$$ 危险。因此,我们可以闪现较高的一个,并获得最多 $$$5$$$ 的最终危险级别。可以证明$$$5$$$是$$$x$$$的最小可能值。
在第二个测试用例中,只有一个电子动画和 $$$32$$$ 的夜间长度。请注意,在这种情况下,电子动画每秒只会增加 $$$1$$$ 的危险。因此,在第 $$$25$$$ 秒之后,我们将其危险重置为 $$$0$$$。距离夜晚结束还有七秒,所以我们最终遇到的危险总是$$$7$$$。
在第三个测试用例中,可以证明$$$x$$$的最小可能值为$$$19$$$。