背景

这道题和上次的不一样。。。

描述

给定n个数a_{1},a_{2},...,a_{n}和一个数k

定义 sum[i,j]=\sum_{x=i}^{j}a_{x} (1\leq i\leq j\leq n, j-i+1 \leq k)

求 sum[i,j] 的最大值

输入格式

第一行有2个数,n,k

第二行有n个数,a_{1},a_{2},...,a_{n}

输出格式

输出只有一行,sum[i,j] 的最大值

样例输入

7 5

3 6 -8 9 -12 1 2

样例输出

10

数据范围与约定

对于50%的数据,n=k(裸裸的送分啊)

对于100%的数据,n\leq 1000000,k\leq n,-1000\leq a_{i}\leq 1000(1\leq i\leq n)

保证答案大于0

样例解释

max\left \{ sum[i,j] \right \}=sum[1,4]=a_{1}+a_{2}+a_{3}+a_{4}=3+6-8+9=10

来源

原创

每个测试点0.5s