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 翻译