Misaka is fighting against an enemy army consisting of ~N~ robots standing in a row, with the ~i^{th}~ robot having a power of ~p_i~. Misaka wants to weaken the enemy army as much as possible by destroying powerful robots, but she can only attack from either the left side or the right side. Fortunately, she has a powerful ability called Railgun that can destroy the ~S~ leftmost robots or the ~S~ rightmost robots.

After using her Railgun ability at most ~T~ times, by how much can she weaken the enemy army's power?

Constraints

~1 \le N \le 10^6~

~1 \le S, T \le N~

~1 \le p_i \le 2000~

~ST < 10^9~

Subtask 1 [2/15]

~1 \le N \le 2000~

The robots are sorted in non-decreasing order in terms of power.

Subtask 2 [9/15]

~1 \le N \le 2000~

~N~ is divisible by ~S~.

Subtask 3 [4/15]

No additional constraints.

Input Specification

The first line of input contains ~3~ space separated integers, ~N~, ~S~, and ~T~.

The second line of input containts ~N~ space separated integers, the power of each robot.

Output Specification

Output a positive integer, the sum of the destroyed robots' powers.

Sample Input 1

5 2 1
1 2 3 4 5

Sample Output 1

9

Explanation for Sample Output 1

Misaka can destroy the ~2~ leftmost robots or the ~2~ rightmost robots. She can weaken the enemy army more by destroying the ~2~ rightmost robots ~(4 + 5 = 9)~.

Sample Input 2

10 2 3
10 1 3 2 9 9 8 9 1 1

Sample Output 2

37

Explanation for Sample Output 2

To attack optimally, Misaka first destroys the ~2~ rightmost robots.

The robots' powers now become: ~10, 1, 3, 2, 9, 9, 8, 9~

Then, she destroys the ~2~ rightmost robots again.

The robots' powers now become: ~10, 1, 3, 2, 9, 9~

Finally, she destroys the ~2~ rightmost robots one more time.

The robots' powers now become: ~10, 1, 3, 2~

In total, she weakened the army by ~(1+1)+(8+9)+(9+9)=37~.

Sample Input 3

11 4 2
9 4 1 3 2 1 3 2 9 1 1

Sample Output 3

30

Explanation for Sample Output 3

To attack optimally, Misaka first destroys the ~4~ rightmost robots.

The robots' powers now become: ~9, 4, 1, 3, 2, 1, 3~

Then, she destroys the ~4~ leftmost robots.

The robots' powers now become: ~2, 1, 3~

In total, she weakened the army by ~(2+9+1+1)+(9+4+1+3)=30~.

Sample Input 4

5 4 5
1 1 1 1 1

Sample Output 4

5

Explanation for Sample Output 4

All robots are destroyed no matter how she attacks.