/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
左右に広がった長さ L の道路があります。この道路上に N 体のゾンビがおり、 i 体目は道路の左端から距離 A_i の地点にいます。 ただし、 L および A_i はすべて偶数です。
あなたはゾンビの餌を K 個持っており、好きな時刻に、道路の両端を含む道路上の好きな位置に餌を置くことができます。 ただし、道路上に同時に 2 つ以上の餌が存在する時刻があってはいけません。 道路上に餌が存在するとき、各ゾンビは餌に向かって単位時間あたり 1 の速さで進みます。ある餌と同じ位置に 1 体以上のゾンビが辿り着いたとき、その餌は食べられて瞬時に消滅します。
道路上に餌が存在しないとき、ゾンビは移動しません。 道路上に餌を置く時刻と位置を適切に定めたときの、道路上に餌が存在する時間の総和の最大値を求めてください。 ただし、答えが整数になることが証明できます。
T 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。
制約
- 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 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
3 2 2 20 4 18 8 9 14 0 2 4 6 8 10 12 14 3 3 140 120 70 20
出力例 1
18 40 160
1 つ目のテストケースについては、以下のように餌を置くのが最適です。
- まず、位置 11 に餌を置く。2 体のゾンビは餌を置いてから 7 単位時間後に同時に位置 11 に到達し、餌を食べる。
- その後、位置 0 に餌を置く。2 体のゾンビは餌を置いてから 11 単位時間後に同時に位置 0 に到達し、餌を食べる。
道路上に餌が存在する時間の総和は 7 + 11 = 18 となります。
Score : 500 points
Problem Statement
There is a road of length L extending left and right. There are N zombies on this road, and the i-th zombie is at a distance of A_i from the left end of the road. Here, L and all A_i are even.
You have K pieces of bait for the zombies, and you can place a piece of bait at any position on the road, including both ends, at any time. However, there must never be a moment when two or more pieces of bait exist on the road simultaneously. When bait exists on the road, each zombie moves toward the bait at a speed of 1 per unit time. When one or more zombies reach the same position as the bait, the bait is eaten and disappears instantly.
When no bait exists on the road, zombies do not move. Find the maximum total amount of time bait exists on the road when the times and positions to place the bait are chosen optimally. It can be proved that the answer is an integer.
You are given T test cases; solve each one.
Constraints
- 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 is even.
- All A_i are even.
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N K L A_1 A_2 \ldots A_N
Output
Output T lines.
The i-th line should contain the maximum total amount of time bait exists on the road for the i-th test case.
Sample Input 1
3 2 2 20 4 18 8 9 14 0 2 4 6 8 10 12 14 3 3 140 120 70 20
Sample Output 1
18 40 160
For the first test case, it is optimal to place the bait as follows.
- First, place bait at position 11. The two zombies simultaneously reach position 11 after 7 units of time and eat the bait.
- Then, place bait at position 0. The two zombies simultaneously reach position 0 after 11 units of time and eat the bait.
The total amount of time bait exists on the road is 7 + 11 = 18.