Problem Background

Little E has unfortunately lost his golden sword in a battle.

Problem Description

Creating a golden sword requires $n$ types of materials, numbered from $1$ to $n$, where the durability value of the material numbered $i$ is $a_i$.

Alchemy is very particular about the order of adding materials, so Little E must add these materials to the alchemy pot in the order from $1$ to $n$.

However, the capacity of the alchemy pot is very limited; it can hold at most $w$ materials.

Fortunately, before adding each material, Little E can remove some materials, but the number cannot exceed $s$.

• We define the durability of the $i$-th material as: the total number of materials in the pot (including the material being added) when the $i$-th material is added $\times\ a_i$, and the durability of the sword is the sum of the durability of all materials.

Little E naturally wants the durability of his sword to be as large as possible so that he can use it in more battles. Please find the maximum durability value.

Note: The "total number of materials in the pot when the $i$-th material is added" includes the material being added to the pot. See the sample cases for detailed information.

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

A single integer on one line, representing the maximum durability value.

Sample Input and Output

Sample Input #1

5 3 3
1 3 2 4 5

Sample Output #1

40

Sample Input #2

5 3 3
1 -3 -2 4 5

Sample Output #2

21

Sample Input #3

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

Sample Output #3

17

Sample Input #4

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

Sample Output #4

-15

Notes

Sample Explanation

• For Sample 1, one possible optimal solution is:
  First, add material 1, now there is $1$ material in the pot, durability is $1 \times a_1 = 1 \times 1 = 1$.
  Then add material 2, now there are $2$ materials in the pot, durability is $2 \times a_2 = 2 \times 3 = 6$.
  Then add material 3, now there are $3$ materials in the pot, durability is $3 \times a_3 = 3 \times 2 = 6$.
  Remove material 1, then add material 4, now there are $3$ materials in the pot, durability is $3 \times a_4 = 3 \times 4 = 12$.
  Remove material 4, then add material 5, now there are $3$ materials in the pot, durability is $3 \times a_5 = 3 \times 5 = 15$.
  The final answer is $1 + 6 + 6 + 12 + 15 = 40$.

• For Sample 2, one possible optimal solution is:
  Add material 1, durability is $1 \times 1 = 1$.
  Remove material 1, add material 2, durability is $1 \times (-3) = -3$.
  Add material 3, durability is $2 \times (-2) = -4$.
  Add material 4, durability is $3 \times 4 = 12$.
  Remove material 2, add material 5, durability is $3 \times 5 = 15$.
  The final answer is $1 + (-3) + (-4) + 12 + 15 = 21$.

• For Sample 3, one possible optimal solution is:
  $a_1 + 2a_2 + 2a_3 + 3a_4 + 4a_5 + 3a_6 + 4a_7 = 17$.

• For Sample 4, one possible optimal solution is:
  $a_1 + a_2 + a_3 + a_4 + a_5 = -15$.

Data Range and Constraints

This problem uses bundled testing.

• Subtask #1 (15 points): $n \leq 10$.
• Subtask #2 (5 points): $n \leq 100$, $a_i \geq 0$.
• 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 additional constraints.

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}$.

见题面 Input 部分

见题面 Output 部分