切蛋糕

题目描述

今天是小Z的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了N个相同的小块,每小块都有对应的幸运值。 小Z作为寿星,自然希望吃到的第一块蛋糕的幸运值总和最大,但小Z最多又只能吃M小块(M≤N)的蛋糕。 吃东西自然就不想思考了,于是小Z把这个任务扔给了学OI的你,请你帮他从这N小块中找出连续的k块蛋糕(k≤M),使得其上的幸运值最大。

输入输出格式

输入格式


输入文件cake.in的第一行是两个整数N,M。分别代表共有N小块蛋糕,小Z最多只能吃M小块。 第二行用空格隔开的N个整数,第i个整数Pi代表第i小块蛋糕的幸运值。

输出格式


输出文件cake.out只有一行,一个整数,为小Z能够得到的最大幸运值。

输入输出样例

输入样例 #1

5 2
1 2 3 4 5

输出样例 #1

9

输入样例 #2

6 3
1 -2 3 -4 5 -6

输出样例 #2

5

说明

对20%的数据,N≤100。   对100%的数据,N≤500000,|Pi|≤500。 答案保证在2^31-1之内。