飴 2 (Candies 2)

問題文

机の上に N 個の飴が横一列に並んでおり，左から順に 1 から N までの番号が付けられている．飴 i (1 ≦ i ≦ N) の美味しさは A_i である．

JOI 君は，N 個の飴のうちいくつかを選んで食べることにした．

ただし，飴を食べ過ぎないために，どの連続する K 個の飴についても，そのうち高々 2 個しか食べないようにする．すなわち，どの j (1 ≦ j ≦ N - K + 1) についても，飴 j から飴 j + K - 1 までの連続する K 個の飴のうち，食べる飴の個数は 2 個以下でなければならない．

このもとで，JOI 君は食べる飴の美味しさの合計をできるだけ大きくしたい．

N 個の飴の美味しさと K が与えられたとき，JOI 君が食べる飴の美味しさの合計の最大値を求めるプログラムを作成せよ．

制約

• 2 ≦ K ≦ N ≦ 3 000．
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．
N K
A₁ A₂ … A_N

出力

標準出力に，JOI 君が食べる飴の美味しさの合計の最大値を 1 行で出力せよ．

入出力例

入力例 1

5 4
1 3 2 4 3

出力例 1

8

JOI 君が飴 1 ，飴 4 ， 飴 5 を食べるとき，美味しさの合計は 8 となる．

どの連続する 4 個の飴についても食べる飴の個数が 2 個以下であるような食べ方のうち，美味しさの合計が 9 以上であるようなものは存在しないため， 8 を出力する．

入力例 2

6 3
3 7 1 5 6 4

出力例 2

21

JOI 君が飴 1 ，飴 2 ， 飴 4 ，飴 5 を食べるとき，美味しさの合計は 21 となる．

どの連続する 3 個の飴についても食べる飴の個数が 2 個以下であるような食べ方のうち，美味しさの合計が 22 以上であるようなものは存在しないため， 21 を出力する．

入力例 3

5 2
3 3 2 2 1

出力例 3

11

入力例 4

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

出力例 4

4427122428

---