A - リンゴ拾い 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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
  • 1 行目には、木の本数を表す整数 N と、連続して収穫できる木の本数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各木に実っているリンゴの個数を表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。

出力

高橋君が収穫したリンゴの個数の合計を 1 行で出力せよ。

入力例 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

Score : 266 pts

Problem Statement

Takahashi is picking apples in an orchard.

There are N apple trees lined up in a row in the orchard, numbered tree 1, tree 2, \ldots, tree N from left to right. Tree i has D_i apples on it.

Takahashi starts from tree 1 and proceeds to the right, harvesting apples according to the following pattern:

  • Harvest apples from K consecutive trees (for each tree he harvests, he picks all the apples on that tree).
  • Immediately after, he skips 1 tree without harvesting, as he is tired and takes a rest.

He repeats this pattern starting from tree 1 until he reaches tree N. If he reaches tree N in the middle of a pattern, he stops there. Takahashi cannot freely choose which trees to harvest or the order in which to harvest them.

Find the total number of apples Takahashi harvests.

For example, when N = 7, K = 3, Takahashi harvests from trees 1, 2, 3, skips tree 4, and harvests from trees 5, 6, 7.

Also, when N = 8, K = 2, Takahashi harvests from trees 1, 2, skips tree 3, harvests from trees 4, 5, skips tree 6, and harvests from trees 7, 8.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
D_1 D_2 \ldots D_N
  • The first line contains an integer N representing the number of trees and an integer K representing the number of consecutive trees that can be harvested, separated by a space.
  • The second line contains integers D_1, D_2, \ldots, D_N representing the number of apples on each tree, separated by spaces.

Output

Print the total number of apples Takahashi harvests on a single line.

Sample Input 1

7 3
5 3 2 8 4 1 6

Sample Output 1

21

Sample Input 2

8 2
3 1 4 1 5 9 2 6

Sample Output 2

18

Sample Input 3

15 4
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150

Sample Output 3

900

Sample Input 4

20 3
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

Sample Output 4

750

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000