新的 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