题目描述

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

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

输入格式

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

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

输出格式

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

样例 1

5 3
2 -5 4 3 -1

6

样例 1 说明

选择区间 $[3,5]$，对应子段 4 3 -1，长度为 $3$，和为 $6$。

样例 2

4 2
1 2 3 4

10

样例 2 说明

可以选择整个序列，长度为 $4$，和为 $10$。注意，长度可以大于 $m$。

数据范围与评分

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

测试组	分值	额外限制
1	20	n <= 200
2	30	n <= 2000
3	50	无

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

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