题目描述

今天是小子 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 $n$ 个相同的小块，每小块都有对应的幸运值。

小子 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小子 Z 最多只能吃 $m (m \le n)$ 小块的蛋糕。

请你帮他从这 $n$ 小块中找出连续的 $k (1 \le k \le m)$ 块蛋糕，使得其上的总幸运值最大。

输入格式

第一行包含两个整数 $n, m$，分别代表共有 $n$ 小块蛋糕，小子 Z 最多只能吃 $m$ 小块。

第二行包含 $n$ 个整数，第 $i$ 个整数 $p_i$ 代表第 $i$ 小块蛋糕的幸运值。

输出格式

仅一行一个整数，即小子 Z 能够得到的最大幸运值。

样例

5 2
1 2 3 4 5

9

样例 1 解释
可以选取长度不超过 $2$ 的连续子段。选取 $[4,5]$ 幸运值和为 $4+5=9$，是所有满足条件的子段中最大的。

6 3
1 -2 3 -4 5 -6

5

样例 2 解释
可以选取长度不超过 $3$ 的连续子段。选取 $[5]$，和为 $5$，为最大。也可以选取 $[5]$ 或 $[3,-4,5]=4$ 等，$5$ 最大。

数据范围与提示

• 对于 $20\%$ 的数据，$1 \le n \le 100$。
• 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$|p_i| \le 500$。
• 保证答案的绝对值在 $[0, 2^{31}-1]$ 之内。

来源

单调队列