004 - 飴 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)．
• 入力される値はすべて整数である．

小課題

1. (4 点) N ≦ 20．
2. (19 点) K ≦ 10．
3. (47 点) N ≦ 300．
4. (30 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．
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

この入力例はすべての小課題の制約を満たす．