该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明有一块很长的面包，显然属于那种长方体切块的，被淘气的弟弟抹上了 n 个相同的小块，每小块都有强度不同的蜂蜜和苦瓜汁。

小明自然希望吃到的面包的的甜蜜度总和最大，但小明最多又只能吃 m(m≤n) 小块的面包。对于甜蜜度的贡献蜂蜜是正的显然苦瓜计是负的，0显然就是纯的面包呀。

请你帮他从这 n 小块中找出连续的k(1≤k≤m) 块面包，使得其上的总甜蜜度最大。

形式化地，在数列 a[1-n] 中，找出一个子段 l,r (r−l+1≤m)，最大化区间和。

输入格式

第一行两个整数 n,m。分别代表共有 n 小块面包，且 最多只能吃 m 小块。

第二行 n 个整数，第 i 个整数 ai代表第 i 小块蛋糕的甜蜜度。

输出格式

仅一行一个整数，即小明能够得到的最大甜蜜度。

输入输出样例

输入 #1

5 2
1 2 3 4 5

输出 #1

9

输入 #2

6 3
1 -2 3 -4 5 -6

输出 #2

5

说明/提示

数据规模与约定

对于 20% 的数据，有 1≤n≤100。

对于 100% 的数据，有 1≤n≤1×10000，∣ai∣≤500。

保证答案的绝对值在 [0,(2<<31)−1] 之内。