注意

この問題は実行時間制限が厳しいので高速な言語を使用することを勧めます。(writer解はPython3ではTLE、PyPy3ではACすることを確認しています。)

問題文

長さ $N$ の数列 $A$ があります。この数列を以下の条件を満たすように $K$ 個の連続部分列 $B_1,B_2,\dots,B_K$ に分割することを考えます。

• $B_1,B_2,\dots,B_K$ はいずれも $A$ の空でない長さ $M$ 以下の連続部分列である。
• $B_1,B_2,\dots,B_K$ をこの順序で連結すると $A$ となる。

ある分割のスコアは $\displaystyle \sum_{i=1}^{K}|\sum_{j=1}^{L_i}B_{i,j}|$ と定義されます。ここで $L_i$ は $B_i$ の長さです。

スコアの最大値を求めてください。

入力

$N\ K\ M$
$A_1\ A_2\ \dots\ A_N$

• 入力は全て整数
• $1 \le N \le 3000$
• $1 \le K,M \le N$
• $N \le M \times K$
• $|A_i| \le 10^9$

出力

スコアの最大値を出力し、最後に改行してください。

サンプル

5 2 4
-7 -7 17 3 -20

26

3 2 2
-6 -15 13

34

9 5 3
17 11 9 -10 -20 5 19 -3 -3

97