P5858 "SWTR-3" Golden Sword

Little E unfortunately lost his golden sword in a battle.

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.

The first line contains three integers $n,w,s$. The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

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

#### "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**](https://pan.baidu.com/s/1erVDllDlvNlEShxh3U42gA). Extraction code: 757d. **The filenames correspond one-to-one with the Subtask numbers.** #### "Source" [Sweet Round 03 D](https://www.luogu.com.cn/contest/24755). Idea & solution: ET2006. Translated by ChatGPT 5