题目背景

小 E 不幸在一场战斗中失去了他的金宝剑。

题目描述

制造一把金宝剑需要 $n$ 种原料，编号为 $1$ 到 $n$，编号为 $i$ 的原料的坚固值为 $a_i$。

炼金是很讲究放入原料的顺序的，因此小 E 必须按照 $1$ 到 $n$ 的顺序依次将这些原料放入炼金锅。

但是，炼金锅的容量非常有限，它最多只能容纳 $w$ 个原料。

所幸的是，每放入一个原料之前，小 E 可以从中取出一些原料，数量不能超过 $s$ 个。

• 我们定义第 $i$ 种原料的耐久度为：放入第 $i$ 种原料时锅内的原料总数（包括正在放入的原料） $\times\ a_i$，则宝剑的耐久度为所有原料的耐久度之和。

小 E 当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。

注：这里的“放入第 $i$ 种原料时锅内的原料总数包括正在放入锅中的原料，详细信息请见样例。

输入格式

第一行，三个整数 $n,w,s$。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示耐久度的最大值。

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

提示

「样例说明」

• 对于样例 1，一种可行的最优方案为： 首先放进原料 1，此时锅内有 $1$ 种原料，耐久度为 $1\times a_1=1\times 1=1$。
  再放进原料 2，此时锅内有 $2$ 种原料，耐久度为 $2\times a_2=2\times 3=6$。
  再放进原料 3，此时锅内有 $3$ 种原料，耐久度为 $3\times a_3=3\times 2=6$。
  取出原料 1，再放进原料 4，此时锅内有 $3$ 种原料，耐久度为 $3\times a_4=3\times 4=12$。
  取出原料 4，再放进原料 5，此时锅内有 $3$ 种原料，耐久度为 $3\times a_5=3\times 5=15$。
  最终答案为 $1+6+6+12+15=40$。
• 对于样例 2，一种可行的最优方案为：
  放进原料 1，耐久度为 $1\times 1=1$。
  取出原料 1，放进原料 2，耐久度为 $1\times (-3)=-3$。
  放进原料 3，耐久度为 $2\times (-2)=-4$。
  放进原料 4，耐久度为 $3\times 4=12$。
  取出原料 2，放进原料 5，耐久度为 $3\times 5=15$。
  最终答案为 $1+(-3)+(-4)+12+15=21$。
• 对于样例 3，一种可行的最优方案为：
  $a_1+2a_2+2a_3+3a_4+4a_5+3a_6+4a_7=17$。
• 对于样例 4，一种可行的最优方案为：
  $a_1+a_2+a_3+a_4+a_5=-15$。

「数据范围与约定」

本题使用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq s \leq w \leq n \leq 5\times 10^3$，$|a_i| \leq 10^9$。对于 Subtask $i$ 有 $|a_i|\leq 10^{i+1}$。

「帮助/说明」

本题下发大样例，具体输入输出见 Big Sample 中的 gold01-08.in/gold01-08.out。提取码：757d。
文件名与 Subtask 编号一一对应。

「来源」

Sweet Round 03 D。
idea & solution：ET2006。