题目描述

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$。