P1169

[Usaco2011 Open]修剪草坪

[Usaco2011 Open]修剪草坪

一年前,FJ 赢得了小镇的最佳草坪比赛,此后他变得十分懒惰,再也没有修剪过草坪。如今,新一届最佳草坪比赛即将开始,FJ 希望能够再次夺冠。

然而,FJ 的草坪已经十分杂乱,他只能安排奶牛完成修剪工作。FJ 有 NN 只排成一列的奶牛,编号为 1,2,…,N1,2,\ldots,N。第 ii 只奶牛的效率值为 EiE_i。

相邻的奶牛彼此十分熟悉。如果 FJ 安排了超过 KK 只连续的奶牛,它们就会罢工并去参加派对。因此,FJ 需要选择一些奶牛,使得任意连续被选择的奶牛数量均不超过 KK,并最大化所选奶牛的效率值之和。

请计算 FJ 能够获得的最大效率值之和。

输入格式

第一行包含两个以空格分隔的整数 NN 和 KK。

接下来 NN 行,第 ii 行包含一个整数 EiE_i,表示第 ii 只奶牛的效率值。

输出格式

输出一个整数,表示 FJ 能够获得的最大效率值之和。

样例输入

5 2
1
2
3
4
5

样例输出

12

样例解释

FJ 有 55 只奶牛,其效率值依次为 1,2,3,4,51,2,3,4,5。在不能选择超过 22 只连续奶牛的条件下,FJ 可以选择除第 33 只以外的所有奶牛,得到的效率值之和为 1+2+4+5=121+2+4+5=12。

数据范围

  • 1≤N≤1051\le N\le 10^5;
  • 1≤K≤N1\le K\le N;
  • 0≤Ei≤1090\le E_i\le 10^9。

来源与许可

本题为 USACO 2011 Open 试题「修剪草坪」,题面与测试数据整理自 BZOJ。

样例 1

输入

5 2
1
2
3
4
5

输出

12