1949:数组魔法阵

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:7 解决:3

题目描述

在蒜头王国的魔法学院里,蒜头君发现了一项古老的魔法试验——"极光之选"。这项试验要求利用一个充满魔力的数组,通过精心挑选出 $k$ 段特定长度的子数组,来汇聚最大的魔法能量,点亮整个魔法阵。现在,蒜头君诚邀你一同参与这顶激动人心的挑战!

你面前摆放着一个由 $n$ 个魔力值组成的数组,每个元素代表着该位置的魔力强度。你的任务是选择 $k$ 段长度均为 $m$ 的连续子数组(这些子数组互不重叠),每段子数组的魔力值之和将被累积,以期达到最大累积魔力值,从而激活 “极光之选” 的终极魔法。

你的魔法任务是运用你的智慧,设计一种策略,选取 $k$ 段长度为 $m$ 的魔力值数组,使得这些子数组的魔力值之和最大化。计算并告知蒜头君,通过最优选择,所能达到的最大累积魔力值是多少。

注意:


  • 数组长度 $n$ 与子数组长度 $m$ 均符合实际魔法操作的限制。
  • 确保所选的每段子数组互不重叠,即任意两段子数组之间没有共同的元素。


输入

第一行包含三个整数 $n,m,k$

第二行包含 $n$ 个整数,代表魔力值数组的魔力值。

$1\le (m\times k)\le n\le 3000$,魔力值在 int 范围内且为正整数。

输出

输出最终的要求答案。

样例输入-1 复制

5 2 1
1 2 3 4 5

样例输出-1 复制

9

样例输入-2 复制

7 1 3
2 10 7 18 5 33 0

样例输出-2 复制

61