C - 果樹園の収穫 解説 /

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

配点 : 366 点

問題文

高橋君は、N 本の果物の木が一列に並んでいる果樹園を訪れました。木には端から順に 1, 2, \ldots, N と番号が付けられており、i 番目の木には A_i 個の果物が実っています。

高橋君は 1 番目の木から N 番目の木まで、番号の小さい順に 1 本ずつ木の前を通っていきます。各木の前を通るのはちょうど 1 回であり、引き返すことはできません。それぞれの木の前を通る際、その木の果物をすべて収穫するか、まったく収穫しないかのどちらかを選びます。一部だけを収穫することはできません。どの木からも収穫しないという選択も許されます。

ただし、ある木で果物を収穫すると、収穫の疲れにより、その木の直後の K 本の木では収穫ができなくなります。すなわち、i 番目の木で収穫した場合、i+1 番目から i+K 番目までの木では収穫できず、次に収穫できるのは i+K+1 番目以降の木です。言い換えると、収穫する木を番号の小さい順に並べたとき、隣り合う任意の 2 つの番号 i, j（i < j）について j \geq i + K + 1 を満たす必要があります。なお、K = 0 の場合はこの制限により連続する木で収穫することも可能です。

高橋君が収穫できる果物の合計個数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N - 1
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、果物の木の本数 N と、収穫後に収穫できなくなる木の本数 K が、スペース区切りで与えられる。
  • 2 行目には、各木に実っている果物の個数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

高橋君が収穫できる果物の合計個数の最大値を 1 行で出力してください。

入力例 1

5 2
3 7 2 5 8

出力例 1

15

入力例 2

8 1
10 20 30 40 50 60 70 80

出力例 2

200

入力例 3

15 3
100 50 30 20 200 10 5 150 80 40 300 25 15 60 250

出力例 3

850

Score : 366 pts

Problem Statement

Takahashi visited an orchard where N fruit trees are lined up in a row. The trees are numbered 1, 2, \ldots, N from one end, and the i-th tree bears A_i fruits.

Takahashi walks past the trees one by one in order from tree 1 to tree N. He passes in front of each tree exactly once and cannot turn back. When passing in front of each tree, he chooses either to harvest all the fruits from that tree or to harvest none at all. He cannot harvest only a portion of the fruits. It is also allowed to harvest from no trees at all.

However, when he harvests fruits from a tree, the fatigue from harvesting prevents him from harvesting at the next K trees immediately after it. That is, if he harvests from the i-th tree, he cannot harvest from trees i+1 through i+K, and the earliest he can next harvest is from tree i+K+1 or later. In other words, if the trees he harvests from are listed in increasing order of their numbers, any two adjacent numbers i, j (i < j) in the list must satisfy j \geq i + K + 1. Note that when K = 0, this restriction allows harvesting from consecutive trees.

Find the maximum total number of fruits that Takahashi can harvest.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N - 1
  • 1 \leq A_i \leq 10^9
  • All inputs are integers.

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains the number of fruit trees N and the number of trees that become unavailable for harvesting after a harvest K, separated by a space.
  • The second line contains the number of fruits on each tree A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print the maximum total number of fruits that Takahashi can harvest, on a single line.

Sample Input 1

5 2
3 7 2 5 8

Sample Output 1

15

Sample Input 2

8 1
10 20 30 40 50 60 70 80

Sample Output 2

200

Sample Input 3

15 3
100 50 30 20 200 10 5 150 80 40 300 25 15 60 250

Sample Output 3

850