2478: 切蛋糕

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

今天是小 Z 的生日,同学们为他带来了一块蛋糕。

这块蛋糕是一个长方体,被用不同色彩分成了 N 个相同的小块,每小块都有对应的幸运值。

小 Z 作为寿星,自然希望吃到的第一块蛋糕的幸运值总和最大,但小 Z 最多又只能吃 M 小块 (M≤N)的蛋糕。

吃东西自然就不想思考了,于是小 Z 把这个任务扔给了学 OI 的你,请你帮他从这 N 小块中找出连续的 k 块蛋糕 (k≤M),使得其上的幸运值最大。


输入格式

第一行包含两个整数 N 和 M,表示共有 N 小块蛋糕,小Z最多只能吃 M 小块。

第二行包含空格隔开的 N 个整数,第 i 个整数 Pi 代表第 i 小块蛋糕的幸运值。

数据范围

1≤N≤500000
−500≤Pi≤500

输出格式

输出包含一个整数,为小 Z 能够得到的最大幸运值。

输入样例 复制

5 2
1 2 3 4 5

输出样例 复制

9

分类标签