← 返回题目列表

AtCoder · awc0055_a

A. 苹果采摘

中文机器翻译题面 查看原题

分数: 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