#P4744. [Wind Festival] Iron Man

[Wind Festival] Iron Man

题目背景

[Midnight - 23:59]

在风筝节上交到了老铁(并不是 Nishikino),接触了 OI,gyx 全身的热情都被点燃啦!!为了更好地参与到下一届风筝节的工作中去,gyx 准备开始为期一年的学习。

题目描述

gyx 想用全部的时间学(tui)OI(fei)!!!

gyx 为了合理的利用所有时间学 OI,他开始规划自己的学习计划。

首先,gyx 的眼里每年有 nn 天,因为 gyx 实在是太想学习啦,所以他并没有留下玩耍的时间(每天都全部用来学 OI 或者文化课),gyx 划分天数的原则是,在每一天中,gyx 对 OI 的感兴趣程度相同。但是,未免 gyx 也会因生活琐事而没法静心学习,所以某些天 gyx 对 OI 的兴趣程度有可能是负的。

然后,gyx 开始安排学习 OI 的时间,gyx 统计出他要学习的OI 知识有 kk 种。因为 gyx 是一个追求完美的人,他认为对于每一种 OI 知识,知识体系的完整性是必要的,某一个部分的 OI 知识学习过程中一旦停下来会影响自己的学习效果,所以他会用连续的一些天来学习一个部分的知识,期间不能停下来学习文化课,也不会穿插着进行几种知识的学习。

但是注意,gyx 在进行每部分 OI 知识的学习之间可以留出一些时间段用来学文化课。并且,gyx 并不介意各个部分 OI 知识间学习的顺序,因为他对每一部分的 OI 知识兴趣程度是相同的。

现在,gyx 想知道他总共用于学 OI 的日子兴趣值之和是多少,因为 gyx 还没有学习过高级的规划算法,所以 gyx 将他学习计划的规划交给你,你可以选择任意一个小于等于 nn 的一个正整数 ii,使他从第 ii 天开始,进行长 nn 天的学习(不一定一开始就必须学 OI),但在这一年中他一定要把清单中所有的知识都学完,gyx 相信你一定能给出兴趣值之和最高的方法。

输入格式

两个正整数 n,kn,k,分别代表 gyx 眼中一年有 nn 天,gyx 要学习的知识有 kk 种。

接下来一行有 nn 个整数,第 ii 个数 aia_i 代表 gyx 第 ii 天对 OI 的兴趣程度。

输出格式

输出一个整数,代表他总共学 OI 的所有日子兴趣值之和最大是多少。

6 2
2 -4 3 -1 2 3

10

提示

样例解释

从第 33 个时间段开始学习,那么他学 OI 的这一年兴趣程度的序列便为:

  • [3,1,2,3,2,4][3,-1,2,3,2,-4]

用于学习两个知识的时间段分别是新序列的第 11 个和第 3,4,53,4,5 个,于是 ans=3+(2+3+2)=10ans=3+(2+3+2)=10

数据范围

  • 对于 10%10\% 的数据,满足 k=1k=1
  • 对于另 30%30\% 的数据,满足 k=2k=2
  • 对于100%100\% 的数据,满足:1k501\le k\le50kn105k\le n\le10^5ai104|a_i|\le 10^4