题目描述

最近新款 iPhone6 发布，乔治很想买，可是他没有足够的钱，所以他打算去当程序员。在工作中他遇到一个问题：
给定一个 n 个整数的序列 \(p_1\),\(p_2\),…,\(p_n\)，选择 k 对整数： \([l_1, r_1]\), \([l_2, r_2]\), …, \([l_k, r_k]\) (1 \(\leq\) \(l_1\) \(\leq\) \(r_1\) < \(l_2\) \(\leq\) \(r_2\) < … < \(l_k\) \(\leq\) \(r_k\) \(\leq\) n; \(r_i\) - \(l_i\) + 1 = m)
求 \(\sum_{i=1}^k\)\(\sum_{j=l_i}^{r_i}\) \(p_j\) 的最大值。

输入格式

第一行三个整数 n, m, k；
第二行 n 个整数 \(p_1\), \(p_2\), …, \(p_n\)。

输出格式

输出最大值

样例1

输入

5 2 1
1 2 3 4 5

输出

9

样例2

输入

7 1 3
2 10 7 18 5 33

输出

61

数据范围

对于 30%的数据，1 \(\leq\) m \(\times\) k \(\leq\) n \(\leq\) 100，0 \(\leq\) \(p_i\) \(\leq\) 100；
对于 100%的数据，1 \(\leq\) m \(\times\) k \(\leq\) n \(\leq\) 5000，0 \(\leq\) \(p_i\) \(\leq\) \(10^9\)。

限制

1s, 256M

样例解释

样例 1：选择区间 \([4, 5]\)，和最大 = 4 + 5 = 9；
样例 2：选择区间 \([2, 2]\)，\([4, 4]\)，\([6, 6]\)，和最大 = 10 + 18 + 33 = 61。

来源

Codeforces467C
CWOI新高二专题测试十五