选择数字

题目描述

给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数,但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入输出格式

输入格式


第一行两个整数n,k 以下n行,每行一个整数表示a[i]。

输出格式


输出一个值表示答案。

输入输出样例

输入样例 #1

5 2
1
2
3
4
5 

输出样例 #1

12

说明

对于20%的数据,n <= 10 对于另外20%的数据, k = 1 对于60%的数据,n <= 1000 对于100%的数据,1 <= n <= 100000,1 <= k <= n,0 <= 数字大小 <= 1,000,000,000 时间限制500ms