题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ 和一个整数 $m$，请选取一段长度至多为 $m$ 的非空连续子段，使其元素之和最大。

即求所有满足 $1\le l\le r\le n$ 且 $1\le r-l+1\le m$ 的区间 $[l,r]$ 中，$a_l+a_{l+1}+\cdots+a_r$ 的最大值。

输入格式

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

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示满足条件的最大子段和。

样例 1

5 2
2 -5 4 3 -1

7

样例 1 说明

选择区间 $[3,4]$，对应子段 4 3，长度为 $2$，和为 $7$。

样例 2

4 3
-8 -2 -5 -4

-2

样例 2 说明

只选择第 $2$ 个数 $-2$。子段不能为空，所以不能输出 $0$。

数据范围与评分

对于所有数据，$1\le m\le n\le200000$，$-10^9\le a_i\le10^9$。

各组独立计分，只有通过一组内的所有测试点，才能获得该组分数。

答案可能超出 32 位整数的范围，请使用 64 位整数类型（如 C++ 的 long long）。