#329. 选数

选数

样例下载

题目描述

NN 个数排成一排,依次为 A1,A2,……,ANA_1, A_2, ……, A_N。

你要从中选取任意个数。

不能有一段超过 MM 个位置连续的数全部被你选走。

如何选取,才能使得所选数的和最大呢?

请你输出这个最大和。

输入格式

第一行:两个整数 N,MN, M

接下来 NN 行:每行一个整数 AiA_i

输出格式

一个整数,表示最大和

样例输入

5 2
1
2
9
4
5

样例输出

16

样例解释

你可以选 2, 9, 5 ,和为 16.

数据范围

共 10 个测试点,每个测试点 10 分。全部测试点满足:1≤N≤105,1≤M≤N,0≤Ai≤1091 ≤ N ≤ 10^5, 1 ≤ M ≤ N, 0 ≤ A_i ≤ 10^9

其中:

有 2 个测试点:1≤N≤101 ≤ N ≤ 10

另有 1 个测试点:M=1M=1