【POJ Challenge】生日礼物

时间限制:10s      空间限制:128MB

题目描述

ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

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


输入格式

第1行,两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。

第2行, N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。


输出格式

 

一个整数,最大的和。


样例输入

 
5 2 
2 -3 2 -1 2

样例输出

5

提示

没有写明提示


题目来源

没有写明来源