問題文

1 から N までの番号のついた N 個のりんごがあります． りんご i のおいしさは A_i です． A_i が負であることもありえます． また，整数 K が与えられます．

あなたは以下の操作を好きな回数 (0 回でもよい) 繰り返すことができます．

• 整数 i (1 \leq i \leq N-K+1) を選び，りんご i,i+1,\cdots,i+K-1 を食べる． なお，以前の操作ですでに食べていたりんごについては何もしない．

最終的にあなたが食べたりんごのおいしさの総和としてありうる最大値を求めてください．

制約

• 1 \leq K \leq N \leq 250000
• -10^9 \leq A_i \leq 10^9
• 入力される値はすべて整数．

入力例 1

4 2
2 -1 2 -2

出力例 1

3

次のような操作が考えられます．

• i=1 を選び，りんご 1,2 を食べる．
• i=2 を選び，りんご 3 を食べる．(りんご 2 はすでに食べているので何もしない)

このとき，食べたりんごのおいしさの総和は A_1+A_2+A_3=3 になります． どのように操作を行っても，食べたりんごのおいしさの総和が 3 を超えることはありません． よって答えは 3 です．

入力例 2

5 5
3 1 4 1 5

出力例 2

14

入力例 3

5 1
-1 -2 -3 -4 -5

出力例 3

0

入力例 4

20 4
573641910 -499039319 421342458 893335602 -961457884 -190195710 -497364364 -954575123 41286305 -310659388 -451608793 122064200 -719921087 87712135 43831420 714154567 -451280 -161259952 488561040 -501663741

出力例 4

2561828581