B - Neutralize

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

N 個の薬品が横一列に並んでいます。それぞれの薬品には 効用 という整数値が定まっており、左から i 番目の薬品の現在の効用は b_i です。これらの値は正とは限りません。

Kenkoooo さんは、横長の特殊な装置を用いて次の操作を何回でも行えます(行わなくても構いません)。

  • 連続して並ぶ K 個の薬品を選ぶ。選ばれた薬品の効用はすべて 0 となる。

なお、薬品を移動させることは危険を伴うためできません。

その後、Kenkoooo さんは N 個の薬品すべてを飲み干します。その前に、N 個の薬品の効用の和を可能な限り大きくしておきたいです。操作後のこの和の最大値を求めてください。

制約

  • 1 ≤ K ≤ N ≤ 2 × 10^5
  • -10^9 ≤ b_i ≤ 10^9
  • 入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
b_1
:
b_N

出力

操作後の N 個の薬品の効用の和の最大値を出力せよ。


入力例 1

9 3
-1
-2
-3
4
5
-6
-7
-8
-9

出力例 1

9

最適な手順の例を示します。

  • 1 回目の操作: 左から 1, 2, 3 番目の薬品を選ぶ。
  • 2 回目の操作: 左から 6, 7, 8 番目の薬品を選ぶ。
  • 3 回目の操作: 左から 7, 8, 9 番目の薬品を選ぶ。

このとき、9 個の薬品の効用の和は 0 + 0 + 0 + 4 + 5 + 0 + 0 + 0 + 0 = 9 となります。


入力例 2

5 4
-1
-1
5
-1
-1

出力例 2

1

何もせずこのまま薬品を飲み干すべきです。


入力例 3

9 5
30
-20
40
60
-90
50
-40
10
70

出力例 3

120

入力例 4

10 1
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000

出力例 4

5000000000