問題文

ある日、sanadaはkaageに N 枚のカードを引くように言われました。
sanadaはとりあえず、言われるがままにカードを引きました。
このカードには表と裏にそれぞれ数が書かれており、2 面に書かれた数の合計は常に M でした。sanadaが引いた N 枚のカードにおいて、i 枚目の表に書かれていた数は A_i です。

次に、kaageは以下の操作を K 回以内の任意の回数（0 回でも可）することを指示しました。

• 1 \leq x\leq y\leq N を満たす任意の整数 x,y を選び、x 枚目から y 枚目までの全てのカードの表裏を反転する。

不審に思ったsanadaは、kaageの家にスパイを送り込み、N 枚のカードの表に書かれた数の合計が多いほどkaageが勉強しなくてはいけないことを知りました。
kaageを勉強させたいsanadaのために、適切な回数・適切な操作を行うことで N 枚のカードの表に書かれた数の合計を最大いくつにできるか求めてください。

制約

• 入力は全て整数である。
• 1 \leq N \leq 10^6
• 0 \leq K \leq N
• 1 \leq M \leq 10^9
• 1 \leq A_i \leq M-1

小課題

1. (400 点) N \leq 2000
2. (400 点) N \leq 10^5
3. (300 点) 追加の制約はない。

入力例1

3 6 1
3 3 4

出力例1

10

この場合、例えば一度も操作を行わないときに、カードの表にある数全ての合計を最大の 10 にできます。

入力例2

8 9 2
1 3 8 7 5 3 5 1

出力例2

52

例えば次のように区間を選んで操作することで、最大値 52 を達成できます。

• 1 回目: 1 枚目から 5 枚目のカードの表裏を反転させる。操作後のカードの並びは {8, 6, 1, 2, 4, 3, 5, 1} となる。
• 2 回目: 3 枚目から 8 枚目のカードの表裏を反転させる。操作後のカードの並びは {8, 6, 8, 7, 5, 6, 4, 8} となる。