← 返回题目列表

Codeforces · 467/C

C. 乔治和乔布

中文机器翻译题面 查看原题

新的 ITone 6 最近发布了,乔治非常想买它。不幸的是,他没有足够的钱,所以乔治打算做一名程序员。现在他在工作中遇到了以下问题。

给定一个由 n 个整数 p1, p2, ..., pn 组成的序列。您要选择 k 对整数:

[l1, r1], [l2, r2], ..., [lk, rk](1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n;ri - li + 1 = m),

使得 sum $$\sum_{i=1}^{k}\sum_{j=l_i}^{r_i}p_j$$ 的值尽可能最大。帮助乔治完成任务。

输入

第一行包含三个整数 n、m 和 k (1 ≤ (m × k) ≤ n ≤ 5000)。第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi ≤ 109)。

输出

在一行中打印一个整数 - sum 的最大可能值。

示例

输入 #1

5 2 1
1 2 3 4 5

输出 #1

9

输入 #2

7 1 3
2 10 7 18 5 33 0

输出 #2

61