#roi49s. 生日礼物

时间限制：1 s       空间限制：256 MiB       标签： 贪心 数据结构 优先队列 链表 POJ Challenge 2011 

算法难度等级：3       思维难度等级：5       实现难度等级：3

题目描述

ftiasch 18 岁生日的时候，lqp18_31 给她看了一个神奇的序列 $a_{1\cdots n}$。她被允许选择不超过 $m$ 个连续的部分作为自己的生日礼物。

自然地，ftiasch 想要知道选择元素之和的最大值。你能帮助她吗？

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_{1\cdots n}$。

输出格式

一行一个整数，表示最大的和。

5 2 
2 -3 2 -1 2

5

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$0\leq m\leq 10^5$，$-10^4\leq a_i\leq 10^4$。