[Usaco2011 Open]修剪草坪
一年前,FJ 赢得了小镇的最佳草坪比赛,此后他变得十分懒惰,再也没有修剪过草坪。如今,新一届最佳草坪比赛即将开始,FJ 希望能够再次夺冠。
然而,FJ 的草坪已经十分杂乱,他只能安排奶牛完成修剪工作。FJ 有 只排成一列的奶牛,编号为 。第 只奶牛的效率值为 。
相邻的奶牛彼此十分熟悉。如果 FJ 安排了超过 只连续的奶牛,它们就会罢工并去参加派对。因此,FJ 需要选择一些奶牛,使得任意连续被选择的奶牛数量均不超过 ,并最大化所选奶牛的效率值之和。
请计算 FJ 能够获得的最大效率值之和。
输入格式
第一行包含两个以空格分隔的整数 和 。
接下来 行,第 行包含一个整数 ,表示第 只奶牛的效率值。
输出格式
输出一个整数,表示 FJ 能够获得的最大效率值之和。
样例输入
5 2
1
2
3
4
5
样例输出
12
样例解释
FJ 有 只奶牛,其效率值依次为 。在不能选择超过 只连续奶牛的条件下,FJ 可以选择除第 只以外的所有奶牛,得到的效率值之和为 。
数据范围
- ;
- ;
- 。
来源与许可
本题为 USACO 2011 Open 试题「修剪草坪」,题面与测试数据整理自 BZOJ。
样例 1
输入
5 2
1
2
3
4
5
输出
12