AT_arc215_a [ARC215A] Zombie

有一条长度为 $L$ 的道路，向左右两侧延伸。在这条路上有 $N$ 个僵尸，第 $i$ 个僵尸距离道路左端 $A_i$ 的位置。这里 $L$ 和所有 $A_i$ 都是偶数。 你有 $K$ 个引诱僵尸的“诱饵”，你可以在道路上的任意位置（包括两端），在任意时刻投放诱饵。但任意时刻，道路上至多只能存在一个诱饵。只要诱饵存在于道路上，所有的僵尸都会以每单位时间 $1$ 的速度朝向诱饵的位置移动。当一只或多只僵尸和诱饵到达同一位置时，诱饵会被瞬间吃掉并消失。 当道路上没有诱饵时，僵尸不移动。请你求出，当投放诱饵的位置和时机都选择最优时，诱饵在道路上存在的总最长时间。可以证明，答案一定为整数。 你将得到 $T$ 个测试用例；请分别解答每个用例。

输入从标准输入读入，格式如下： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试用例如下格式： > $N$ $K$ $L$ $A_1$ $A_2$ $\ldots$ $A_N$

输出共 $T$ 行。 第 $i$ 行输出第 $i$ 个测试用例的诱饵在道路上存在的最长总时间。

### 样例解释 1 对于第一个测试用例，最优方案如下： - 首先，在位置 $11$ 处投放诱饵。两只僵尸均需经过 $7$ 单位时间才能到达 $11$，这时诱饵被吃掉。 - 然后，在位置 $0$ 处投放诱饵。两只僵尸均需经过 $11$ 单位时间才能到达 $0$，这时诱饵被吃掉。 总共诱饵存在的时间为 $7+11=18$。 ### 数据范围 - $1 \le T \le 10^5$ - $1 \le N \le 2 \times 10^5$ - $1 \le K \le 10^9$ - $2 \le L \le 10^9$ - $0 \le A_i \le L$ - $L$ 为偶数 - 所有 $A_i$ 为偶数 - 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$ - 所有输入数值均为整数。 由 ChatGPT 5 翻译