B - りんご収穫 解説 /

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

配点 : 333 点

問題文

高橋君は果樹園を経営しています。果樹園には N 本のりんごの木が一列に並んでおり、左から順に木 1, 木 2, \ldots, 木 N と番号が付けられています。木 i には H_i 個のりんごが実っています。

高橋君は、収穫作業の効率化のため、連続する木の番号の範囲を表す整数の組 (L, R)（1 \leq L \leq R \leq N）を 1 つ選び、木 L から木 R までのすべての木からりんごを収穫します。ただし、作業員の人数の都合上、区間に含まれる木の本数 R - L + 1 は M 以下でなければなりません。ここで M は、一度の収穫作業で扱える木の最大本数です。

収穫したりんごのうち、市場に出荷できるのは出荷基準を満たす木のりんごだけです。具体的には、木 L から木 R までの木 i について、H_i \geq K を満たす木のりんごのみが出荷対象となります。出荷対象の木からは、その木に実っているりんご H_i 個すべてが出荷されます。出荷できるりんごの総数は、これらの出荷対象の木の H_i の合計です。出荷基準を満たす木が区間内に 1 本もない場合、出荷できるりんごの総数は 0 です。

高橋君が (L, R) を最適に選んだとき、出荷できるりんごの総数の最大値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • 1 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9
  • 入力はすべて整数である

入力

N M K
H_1 H_2 \ldots H_N
  • 1 行目には、木の本数を表す整数 N、一度の収穫作業で扱える木の最大本数を表す整数 M、出荷基準となるりんごの個数の下限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各木に実っているりんごの個数を表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

出荷できるりんごの総数の最大値を 1 行で出力せよ。

入力例 1

5 3 5
3 7 2 8 6

出力例 1

15

入力例 2

4 2 10
3 5 2 1

出力例 2

0

入力例 3

10 4 3
1 5 0 4 7 2 9 3 1 6

出力例 3

20

入力例 4

20 6 5
2 8 1 10 3 7 0 15 6 4 12 5 9 2 11 3 8 1 7 6

出力例 4

47

入力例 5

1 1 1
1000000000

出力例 5

1000000000

Score : 333 pts

Problem Statement

Takahashi runs an orchard. The orchard has N apple trees lined up in a row, numbered tree 1, tree 2, \ldots, tree N from left to right. Tree i has H_i apples growing on it.

To streamline the harvesting process, Takahashi will choose one pair of integers (L, R) (1 \leq L \leq R \leq N) representing a range of consecutive tree numbers, and harvest apples from all trees from tree L to tree R. However, due to the limited number of workers, the number of trees in the range, R - L + 1, must be at most M, where M is the maximum number of trees that can be handled in a single harvesting operation.

Among the harvested apples, only apples from trees that meet the shipping standard can be shipped to market. Specifically, for tree i from tree L to tree R, only apples from trees satisfying H_i \geq K are eligible for shipping. From each eligible tree, all H_i apples growing on that tree are shipped. The total number of apples that can be shipped is the sum of H_i over all eligible trees. If there are no trees meeting the shipping standard within the range, the total number of apples that can be shipped is 0.

Find the maximum total number of apples that can be shipped when Takahashi chooses (L, R) optimally.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • 1 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9
  • All input values are integers

Input

N M K
H_1 H_2 \ldots H_N
  • The first line contains the integer N representing the number of trees, the integer M representing the maximum number of trees that can be handled in a single harvesting operation, and the integer K representing the minimum number of apples required to meet the shipping standard, separated by spaces.
  • The second line contains the integers H_1, H_2, \ldots, H_N representing the number of apples growing on each tree, separated by spaces.

Output

Print the maximum total number of apples that can be shipped, on a single line.

Sample Input 1

5 3 5
3 7 2 8 6

Sample Output 1

15

Sample Input 2

4 2 10
3 5 2 1

Sample Output 2

0

Sample Input 3

10 4 3
1 5 0 4 7 2 9 3 1 6

Sample Output 3

20

Sample Input 4

20 6 5
2 8 1 10 3 7 0 15 6 4 12 5 9 2 11 3 8 1 7 6

Sample Output 4

47

Sample Input 5

1 1 1
1000000000

Sample Output 5

1000000000