Note

This problem has a strict execution time limit, so we recommend using a fast language. (It has been confirmed that the writer's solution gets TLE in Python3 and AC in PyPy3.)

Problem Statement

There is a sequence $A$ of length $N$. Consider partitioning this sequence into $K$ contiguous subarrays $B_1,B_2,\dots,B_K$ so that the following conditions are satisfied.

• Each of $B_1,B_2,\dots,B_K$ is a non-empty contiguous subarray of $A$ of length at most $M$.
• Concatenating $B_1,B_2,\dots,B_K$ in this order yields $A$.

The score of a partition is defined as $\displaystyle \sum_{i=1}^{K}|\sum_{j=1}^{L_i}B_{i,j}|$, where $L_i$ is the length of $B_i$.

Find the maximum score.

Input

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

• All input values are integers.
• $1 \le N \le 3000$
• $1 \le K,M \le N$
• $N \le M \times K$
• $|A_i| \le 10^9$

Output

Output the maximum score, followed by a newline.

Sample

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