飴 2 (Candies 2)

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

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

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

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

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

• \(2 \leqq K \leqq N \leqq 3\,000\)．
• \(1 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
• 入力される値はすべて整数である．

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

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

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

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

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

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

JOI 2022 · JCIOI · CC BY-SA 4.0

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

\(N\) \(K\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)

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