题目描述

高桥的房子里有 $N$ 个按顺序排列的面板，编号从 $1$ 到 $N$。第 $i$ 个面板上有一个数字 $A_i$。高桥正在玩一个游戏，他要往这些面板上投掷球。

高桥共投掷了 $K$ 次球。假设第 $i$ 次投掷击中了面板 $p_i$，他将第 $i$ 次投掷的得分设为 $i \times A_{p_i}$。

他准备计算自己的投掷得分总和，但他忘记了每次投掷击中的面板 $p_1, p_2, ..., p_K$。他唯一记得的是对于每个 $i$ $(1 ≤ i ≤ K-1)$，都满足 $1 ≤ p_{i+1}-p_i ≤ M$。基于这个事实，找出他的投掷得分的最大可能总和。

约束条件

• $1 ≤ M ≤ N ≤ 100,000$
• $1 ≤ K ≤ min(300,N)$
• $1 ≤ A_i ≤ 10^{9}$

部分分数

• 在价值为 $100$ 分的测试集中，$M = N$。
• 在价值为另外 $200$ 分的测试集中，$N ≤ 300$ 且 $K ≤ 30$。
• 在价值为另外 $300$ 分的测试集中，$K ≤ 30$。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $K$ $A_1$ $A_2$ … $A_N$

输出

输出高桥投掷得分的最大可能总和。

示例输入 1

5 2 3
10 2 8 10 2

示例输出 1

56

在面板 $1,3$ 和 $4$ 以这个顺序被击中时，得分总和最大。

示例输入 2

5 5 2
5 2 10 5 9

示例输出 2

28

该示例满足部分得分的额外约束条件 $M = N$。

示例输入 3

10 3 5
3 7 2 6 9 4 8 5 1 1000000000

示例输出 3

5000000078