描述

ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。ftiasch想要知道选择元素之和的最大值。你能帮助她吗?

输入格式

第一行两个整数N,M。

第二行N个整数A1~AN。

输出格式

一个整数,表示答案。

样例输入

5 2 
2 -3 2 -1 2

样例输出

5

数据范围与约定

  • 对于100%的数据: N,M<=10^5, |Ai|<=10^4

来源

北京大学