分数: 266 分
问题陈述
高桥正在果园里摘苹果。
有 N 苹果树在果园里排成一排,编号树 1,树 2, \ldots,树 N 从左到右。树 i 有 D_i 苹果就可以了。
高桥从树开始 1 然后向右前进,按照以下模式收获苹果:
- 收获苹果 K 连续的树(对于他收获的每棵树,他都会采摘该树上的所有苹果)。
- 紧接着,他跳过了 1 树没有收获,因为他累了,需要休息。
他从树开始重复这个模式 1 直到他到达树 N。如果他到达树上 N 在一个模式的中间,他停在那里。高桥无法自由选择采伐哪些树木或采伐顺序。
求高桥收获的苹果总数。
例如,当 N = 7, K = 3,高桥从树上收获 1, 2, 3,跳过树 4,以及从树上收获 5, 6, 7.
另外,当 N = 8, K = 2,高桥从树上收获 1, 2,跳过树 3,从树上收获 4, 5,跳过树 6,以及从树上收获 7, 8.
约束
- 1 \leq N \leq 10^6
- 1 \leq K \leq N
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数。
输入
N K D_1 D_2 \ldots D_N
- 第一行包含一个整数 N 表示树的数量和一个整数 K 代表可以采伐的连续树木的数量,以空格分隔。
- 第二行包含整数 D_1, D_2, \ldots, D_N 代表每棵树上的苹果数量,以空格分隔。
输出
在一行上打印 Takahashi 收获的苹果总数。
示例输入 1
7 3 5 3 2 8 4 1 6
示例输出 1
21
示例输入 2
8 2 3 1 4 1 5 9 2 6
示例输出 2
18
示例输入 3
15 4 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
示例输出 3
900
示例输入 4
20 3 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
示例输出 4
750
示例输入 5
1 1 1000000000
示例输出 5
1000000000