某公司 n 天有值班任务,第 i 天的**报酬**是 p_i。
员工可以报名若干个**连续的实习期**:每个实习期恰好覆盖**连续的 m 天**,报酬就是这 m 天报酬之和。要求:
- 一共报名**恰好 k 个**实习期;
- 任意两个实习期**不能有任何一天重叠**;
- 一天最多属于一个实习期(不参加的天没有报酬)。
问能拿到的**报酬总和最大值**。
第一行**三个整数 n、m、k**(注意顺序:先每段长度 m,再段数 k)。
第二行 n 个整数 p_i。
一行一个整数:k 段互不重叠的长度为 m 的连续区间之和的最大值。末尾换行。
5 2 1 1 2 3 4 5
9
7 1 3 2 10 7 18 5 33 0
61
**样例 #1 解释**
每段长 m=2、只选 k=1 段。长度 2 的区间和依次是 3,5,7,9,最大是第 4,5 天这段,4+5=9。
**样例 #2 解释**
m=1(每段只有 1 天)、k=3(挑 3 天),取最大的三个 33+18+10=61。
| t1 | 20 | 20 | 3\le n\le8, 1\le m\le3, 1\le k\le3 |
| t2 | 20 | 40 | 14\le n\le18, 1\le m\le4, 2\le k\le5 |
| t3 | 20 | 60 | 30\le n\le36, 1\le m\le4, 4\le k\le12 |
| t4 | 20 | 80 | 800\le n\le1000, 1\le m\le5, 8\le k\le40 |
| t5 | 20 | 100 | n=5000, p_i\le10^9(约每 4 组一次 m=1 且 k 接近 n) |
| 时间限制 | 1 秒 |
| 内存限制 | 512 MB |