4444. 果蝇诱饵

题目描述

有一条长度为 $L$ 的笔直道路，左右延伸。道路上有 $N$ 只果蝇，第 $i$ 只果蝇位于距离道路左端 $A_i$ 的位置。这里，$L$ 和所有 $A_i$ 均为偶数。

你有 $K$ 块诱饵，可以随时在道路上的任意位置（包括两端）放置一块诱饵。但任何时候都不允许同时存在两块或更多块诱饵。当诱饵存在于道路上时，每只果蝇都会以每秒 $1$ 单位的速度向诱饵移动。当有一只或多只果蝇到达诱饵所在位置时，诱饵立即被吃掉并消失。

当道路上没有诱饵时，果蝇静止不动。请合理选择放置诱饵的时间和位置，使得诱饵存在于道路上的总时间最长。可以证明答案是一个整数。

给定 $T$ 组测试数据，请分别求解。

输入格式

输入从标准输入读入。第一行给出一个整数 $T$，代表测试数据的总组数。随后依次给出 $T$ 组数据，每组数据包含两行信息：
第一行为三个整数 $N, K, L$，依次表示果蝇数量、诱饵块数以及道路长度；
第二行为 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每只果蝇到道路左端的距离。
所有输入值均为整数。

输出格式

输出共 $T$ 行。对于第 $i$ 组测试数据，输出一行，包含一个整数，表示该组数据中诱饵能够存在于道路上的最大可能总时间。

输入输出样例 #1

输入

3
2 2 20
4 18
8 9 14
0 2 4 6 8 10 12 14
3 3 140
120 70 20

输出

18
40
160

大样例1-2

大样例

说明 / 提示

样例解释 1

对于第一个测试用例，最优放置方案如下：

• 首先，将诱饵放在位置 $11$。两只果蝇同时经过 $7$ 个单位时间后到达位置 $11$，吃掉诱饵。
• 然后，将诱饵放在位置 $0$。两只果蝇同时经过 $11$ 个单位时间后到达位置 $0$，吃掉诱饵。

诱饵存在的总时间为 $7 + 11 = 18$。

数据范围与提示

• 对于 $5\%$ 的数据：$N = 1$。
• 对于另外 $5\%$ 的数据：$K = 1$。
• 对于另外 $10\%$ 的数据：$L = 30$ 且 $K = 5, T = 1$。
• 对于另外 $10\%$ 的数据：$N < K$。
• 对于 $100\%$ 的数据：$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$。所有输入均为整数。