George 与工作

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定包含 $n$ 个非负整数的序列 $p_1,p_2,\ldots,p_n$。选择恰好 $k$ 个两两不重叠的连续子段，每个子段长度都为 $m$，求这些子段中所有元素之和的最大值。两个子段可以首尾相邻，但不能共享元素。

输入格式

第一行包含 $n,m,k$。第二行包含 $n$ 个整数 $p_1,\ldots,p_n$。

输出格式

输出最大总和。

样例输入 1

5 2 1
1 2 3 4 5

样例输出 1

9

样例输入 2

7 1 3
2 10 7 18 5 33 0

样例输出 2

61

数据范围

$1\le m\times k\le n\le5000$，$0\le p_i\le10^9$。