Background

Little E unfortunately lost his golden sword in a battle.

Problem Description

To make a golden sword, $n$ kinds of materials are needed, numbered from $1$ to $n$. The sturdiness value of material $i$ is $a_i$.

Alchemy pays great attention to the order of adding materials, so Little E must add these materials into the alchemy pot in the order from $1$ to $n$, one by one.

However, the pot has a very limited capacity: it can hold at most $w$ materials.

Fortunately, before adding each material, Little E may take out some materials from the pot, but the number taken out cannot exceed $s$.

• We define the durability of material $i$ as: (the total number of materials in the pot when adding material $i$, including the material being added) $\times\ a_i$. Then, the sword's durability is the sum of the durabilities of all materials.

Little E of course wants his sword's durability to be as large as possible, so that he can take it into more battles. Please output the maximum possible durability.

Note: Here, “the total number of materials in the pot when adding material $i$” includes the material currently being put into the pot. For details, see the samples.

Input Format

The first line contains three integers $n,w,s$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

Output Format

Output one integer in one line, representing the maximum durability.

5 3 3
1 3 2 4 5

40

5 3 3
1 -3 -2 4 5

21

7 4 2
-5 3 -1 -4 7 -6 5

17

5 3 1
-1 -3 -2 -4 -5

-15

Hint

"Sample Explanation"

• For Sample 1, one feasible optimal plan is: First put in material 1. Now there is $1$ material in the pot, and the durability is $1\times a_1=1\times 1=1$.
  Then put in material 2. Now there are $2$ materials in the pot, and the durability is $2\times a_2=2\times 3=6$.
  Then put in material 3. Now there are $3$ materials in the pot, and the durability is $3\times a_3=3\times 2=6$.
  Take out material 1, then put in material 4. Now there are $3$ materials in the pot, and the durability is $3\times a_4=3\times 4=12$.
  Take out material 4, then put in material 5. Now there are $3$ materials in the pot, and the durability is $3\times a_5=3\times 5=15$.
  The final answer is $1+6+6+12+15=40$.
• For Sample 2, one feasible optimal plan is:
  Put in material 1, and the durability is $1\times 1=1$.
  Take out material 1, put in material 2, and the durability is $1\times (-3)=-3$.
  Put in material 3, and the durability is $2\times (-2)=-4$.
  Put in material 4, and the durability is $3\times 4=12$.
  Take out material 2, put in material 5, and the durability is $3\times 5=15$.
  The final answer is $1+(-3)+(-4)+12+15=21$.
• For Sample 3, one feasible optimal plan is:
  $a_1+2a_2+2a_3+3a_4+4a_5+3a_6+4a_7=17$.
• For Sample 4, one feasible optimal plan is:
  $a_1+a_2+a_3+a_4+a_5=-15$.

"Constraints and Notes"

This problem uses bundled testdata.

• Subtask #1 (15 points): $n\leq 10$.
• Subtask #2 (5 points): $n\leq 100$, $a_i\geq0$.
• Subtask #3 (15 points): $n\leq 300$.
• Subtask #4 (15 points): $s=w=n$.
• Subtask #5 (5 points): $a_i\geq 0$.
• Subtask #6 (10 points): $n\leq 2\times 10^3$.
• Subtask #7 (10 points): $s=1$.
• Subtask #8 (25 points): no special restrictions.

For $100\%$ of the data, $1 \leq s \leq w \leq n \leq 5\times 10^3$, $|a_i| \leq 10^9$. For Subtask $i$, $|a_i|\leq 10^{i+1}$.

"Help / Notes"

This problem provides large samples. For the exact input and output, see gold01-08.in / gold01-08.out in Big Sample. Extraction code: 757d.
The filenames correspond one-to-one with the Subtask numbers.

"Source"

Sweet Round 03 D.
Idea & solution: ET2006.

Translated by ChatGPT 5