#2288. 【POJ Challenge】生日礼物

题目描述

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

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


输入格式

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

第2行， N 个整数 A 1, A 2, ..., A N (0 ≤ | A i| ≤ 104), 序列。

输出格式

一个整数，最大的和。

样例

样例输入

5 2   

2 -3 2 -1 2  

样例输出

5  

数据范围与提示