Problem Description

At Takahashi's house, there are panels arranged in a row, numbered $1, 2, ..., N$. Each panel $i$ has a number $A_i$ written on it, and Takahashi plays by hitting these panels with a ball.

Takahashi has thrown the ball $K$ times. When Takahashi hit the panel $p_i$ on the $i$-th throw, he defined the score of this game as the sum of $i \times A_{p_i}$.

Now, Takahashi has finished throwing the ball $K$ times and is about to calculate his score, but he forgot the panels $p_1, p_2, ..., p_K$ he hit. The only thing he remembers is that for all $i$ satisfying $1 ≦ i ≦ K-1$, $1 ≦ p_{i+1} - p_i ≦ M$ held. Based on this information, find the maximum possible score Takahashi could have achieved.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the maximum possible score Takahashi could have achieved.

Sample Input and Output

Sample Input #1

5 2 3
10 2 8 10 2

Sample Output #1

56

Sample Input #2

5 5 2
5 2 10 5 9

Sample Output #2

28

Sample Input #3

10 3 5
3 7 2 6 9 4 8 5 1 1000000000

Sample Output #3

5000000078

Notes/Hints

Constraints

• $ 1 ≦ M ≦ N ≦ 10^5 $
• $ 1 ≦ K ≦ min(300, N) $
• $ 1 ≦ A_i ≦ 10^{9} $

Partial Points

• For a dataset worth $100$ points, $M = N$ holds.
• For a dataset worth $200$ points, $N ≦ 300, K ≦ 30$ holds.
• For a dataset worth $300$ points, $K ≦ 30$ holds.

Sample Explanation 1

Hitting panels $1, 3, 4$ in this order yields the maximum score.

Sample Explanation 2

This input satisfies the partial point constraint of $M = N$.

见题面 Input 部分

见题面 Output 部分