[Wind Festival]Iron Man

题目背景

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

题目描述

$gyx$想用全部的时间学$(tui)OI(fei)$!!! $gyx$为了合理的利用所有时间学$OI$,他开始规划自己的学习计划。 首先,$gyx$的眼里每年有$n$天,因为$gyx$实在是太想学习啦,所以他并没有留下玩耍的时间(每天都全部用来学$OI$或者文化课),$gyx$划分天数的原则是,在每一天中,$gyx$对$OI$的感兴趣程度相同。但是,未免$gyx$也会因生活琐事而没法静心学习,所以某些天$gyx$对$OI$的兴趣程度有可能是负的。 然后,$gyx$开始安排学习$OI$的时间,$gyx$统计出他要学习的$OI$知识有$k$种。因为$gyx$是一个追求完美的人,他认为对于每一种$OI$知识,知识体系的完整性是必要的,某一个部分的$OI$知识学习过程中一旦停下来会影响自己的学习效果,所以他会用连续的一些天来学习一个部分的知识,期间不能停下来学习文化课,也不会穿插着进行几种知识的学习。 但是注意,$gyx$在进行每部分$OI$知识的学习之间可以留出一些时间段用来学文化课。并且,$gyx$并不介意各个部分$OI$知识间学习的顺序,因为他对每一部分的$OI$知识兴趣程度是相同的。 现在,$gyx$想知道他总共用于学$OI$的日子兴趣值之和是多少,因为$gyx$还没有学习过高级的规划算法,所以$gyx$将他学习计划的规划交给你,你可以选择任意一个小于等于$n$的一个正整数$i$,使他从第$i$天开始,进行长$n$天的学习(不一定一开始就必须学$OI$),但在这一年中他一定要把清单中所有的知识都学完,$gyx$相信你一定能给出兴趣值之和最高的方法。

输入输出格式

输入格式


两个正整数$n$,$k$,分别代表$gyx$眼中一年有$n$天,$gyx$要学习的知识有$k$种 接下来一行有$n$个整数,第$i$个数$a_i$代表$gyx$第$i$天对$OI$的兴趣程度

输出格式


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

输入输出样例

输入样例 #1

6 2
2 -4 3 -1 2 3

输出样例 #1

10

说明

样例解释: 从第$3$个时间段开始学习,那么他学$OI$的这一年兴趣程度的序列便为: $3$,$-1$,$2$,$3$,$2$,$-4$ 用于学习两个知识的时间段分别是新序列的第$1$个和第$3,4,5$个, $ans=3+(2+3+2)=10$; 数据范围: 对于$10\%$的数据,满足$k=1$; 对于另$30\%$的数据,满足$k=2$; 对于$100\%$的数据,满足:$1\le k\le50$; $k\le n\le10^5$; $|a_i|\le10^4$;