AT_arc215_a [ARC215A] Zombie

左右に広がった長さ $ L $ の道路があります。この道路上に $ N $ 体のゾンビがおり、 $ i $ 体目は道路の左端から距離 $ A_i $ の地点にいます。 ただし、 $ L $ および $ A_i $ はすべて偶数です。 あなたはゾンビの餌を $ K $ 個持っており、好きな時刻に、道路の両端を含む道路上の好きな位置に餌を置くことができます。 ただし、道路上に同時に $ 2 $ つ以上の餌が存在する時刻があってはいけません。 道路上に餌が存在するとき、各ゾンビは餌に向かって単位時間あたり $ 1 $ の速さで進みます。ある餌と同じ位置に $ 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 $ 番目のテストケースについて、道路上に餌が存在する時間の総和の最大値を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについては、以下のように餌を置くのが最適です。 - まず、位置 $ 11 $ に餌を置く。 $ 2 $ 体のゾンビは餌を置いてから $ 7 $ 単位時間後に同時に位置 $ 11 $ に到達し、餌を食べる。 - その後、位置 $ 0 $ に餌を置く。 $ 2 $ 体のゾンビは餌を置いてから $ 11 $ 単位時間後に同時に位置 $ 0 $ に到達し、餌を食べる。 道路上に餌が存在する時間の総和は $ 7 + 11 = 18 $ となります。 ### 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 $ は偶数 - $ A_i $ はすべて偶数 - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数