[AdditionalFile6489.zip](file://AdditionalFile6489.zip?type=additional_file)

#6489. 生日礼物

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

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