Flipping Signs 2

この問題はFlipping Signsを元に作られたものです

まずはこちらから解くことをおすすめします

問題文

$N$ 個の整数が並んでおり、順に $A_1,A_2,...,A_N$です。

あなたはこの整数列に対して次の操作を好きなだけ行うことができます。

操作: $1\leq i\leq N-K+1$ を満たす整数 $i$ を選ぶ。$A_i,A_{i+1},...,A_{i+K-1}$ に $-1$ を乗算する。

操作終了後の整数列を $B_1,B_2,..,B_N$ とします。

$B_1+B_2+...+B_N$ の最大値を求めてください。

制約

• 入力は全て整数である。
• $1 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $-10^9\leq A_i \leq 10^9$

入力

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

N K
A_1 A_2 ... A_N

出力

$B_1+B_2+...+B_N$ の最大値を出力せよ。

入力例1

3 2
-10 5 -4

出力例1

19