题目描述

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。

注意：子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n, m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

样例

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

样例解释

序列为：1, -3, 5, 1, -2, 3

长度不超过 4 的最大子序列：5 + 1 + (-2) + 3 = 7，长度为 4。

也可以取 5 + 1 = 6，但 7 更大。

数据范围

• $1 \le n, m \le 300000$
• 保证所有输入和最终结果都在 int 范围内。

时空限制

• 时间限制：1 秒
• 空间限制：64 MB