#P1368. 鱼儿仪仗队

鱼儿仪仗队

【问题描述】

池塘里有很多条鱼,鱼儿们现在决定组成一个仪仗队。现在备选的N(1 <= N <= 100,000)条鱼排成了一条直线,并且按照亲近关系排的队伍,鱼儿的顺序不能改变,现在知道每条鱼的魅力值是Xi(0 <=Xi <= 1,000,000,000)。

挑选仪仗队的任务交给了小x手里(小x并不是鱼),小x发现,如果连续的挑选超过K条鱼,那么这些鱼因为关系太好,结成小团队,影响仪仗队的团结。

所以,小x挑选仪仗队的唯一原则是不能连续挑选超过K条鱼,现在小x想知道,组成仪仗队的鱼儿的最大的魅力值之和是多少。

【输入格式】guard.in

第一行:两个整数N和K

接下来N行,每行一个整数Xi,表示第i条鱼的魅力值。

【输出格式】guard.out

一个整数,表示仪仗队最大的魅力值之和。

【输入样例】

5 2
1
2
3
4
5

【输出样例】

12

不选第3条鱼,魅力值之和是1+2+4+5

【数据范围】

60% 数据保证 N<=10000

最大范围如题目描述。