配点 : $400$ 点

問題文

$N$ 個のマスが横一列に並んでいます。 左から $i$ 番目のマスには整数 $a_i$ が書かれています。

最初、すべてのマスは白色です。 すぬけ君は次の操作を好きな回数だけ繰り返します。

• 連続する $K$ 個のマスを選び、それらすべてを白く塗るか、それらすべてを黒く塗る。 このとき、各マスの色は上書きされる。

すぬけ君が操作を終えた後、黒いマスに書かれた整数の総和がスコアになります。 考えられるスコアの最大値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $a_i$ は整数である。
• $|a_i| \leq 10^9$

入力

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

$N$ $K$

$a_1$ $a_2$ $...$ $a_N$

出力

考えられるスコアの最大値を出力せよ。

5 3
-10 10 -10 10 -10

10

左から $2$, $3$, $4$ 番目のマスを黒く塗ればよいです。

4 2
10 -10 -10 10

20

たとえば、次のように操作を行えばよいです。

• 左から $1$, $2$ 番目のマスを黒く塗る。
• 左から $3$, $4$ 番目のマスを黒く塗る。
• 左から $2$, $3$ 番目のマスを白く塗る。

1 1
-10

0

10 5
5 -4 -5 -8 -4 7 2 -4 0 7

17