题目描述

翰翰 18 岁生日的时候，达达给她看了一个神奇的序列 $A_1,A_2,…,A_N$。

她被允许从中选择不超过 $M$ 个连续的部分作为自己的生日礼物。

翰翰想要知道选择元素之和的最大值。

你能帮助她吗？

输入格式

第一行包含两个整数 $N,M$。

第二行包含$N$个整数 $A_1∼A_N$。

输出格式

输出一个整数，表示答案。

样例

5 2 
2 -3 2 -1 2

5

数据范围

• $1≤N,M≤10^5$
• $|A_i|≤10^4$

来源

• BZOJ2288
• 算法竞赛进阶指南