题目描述

给定一行$n$个非负整数$a_1 \dots a_n$。现在你可以选择其中若干个数，但不能有超过$k$个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入格式

第一行两个整数$n$，$k$

$\\$以下$n$行，每行一个整数表示$a_i$。

输出格式

输出一个值表示答案。

5 2
1
2
3
4
5 

12

数据规模与约定

对于20%的数据，n <= 10

对于另外20%的数据， k = 1

对于60%的数据，n <= 1000

对于100%的数据，1 <= n <= 100000，1 <= k <= n，0 <= 数字大小 <= 1,000,000,000