Description

[洛谷 P1714]

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

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

小Z希望吃到的蛋糕的幸运值总和最大，但小Z最多又只能吃M小块(M≤N)的蛋糕。

请你帮他从这N小块中找出连续的k块蛋糕(k≤M)，使得其上的幸运值最大。

Input Format

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

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

数据范围：

1 ≤ N ≤ 500000

−500 ≤ Pi ≤ 500

Output Format

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

5 2
1 2 3 4 5​

9​

6 3
1 -2 3 -4 5 -6

5

Hint

题意分析：

在长度为N的区间里找一个长度不超过M的区间,要求区间和最大。

Source

单调队列