飴 2 (Candies 2)
시간 제한2초메모리 제한1024 MB
연속한 K개의 사탕 중 최대 2개만 고르는 조건에서 고른 사탕의 맛 합의 최댓값을 구한다.
문제
机の上に N 個の飴が横一列に並んでおり，左から順に 1 から N までの番号が付けられている．飴 i (1 ≦ i ≦ N) の美味しさは Ai である．
JOI 君は，N 個の飴のうちいくつかを選んで食べることにした．
ただし，飴を食べ過ぎないために，どの連続する K 個の飴についても，そのうち高々 2 個しか食べないようにする．すなわち，どの j (1 ≦ j ≦ N - K + 1) についても，飴 j から飴 j + K - 1 までの連続する K 個の飴のうち，食べる飴の個数は 2 個以下でなければならない．
このもとで，JOI 君は食べる飴の美味しさの合計をできるだけ大きくしたい．
N 個の飴の美味しさと K が与えられたとき，JOI 君が食べる飴の美味しさの合計の最大値を求めるプログラムを作成せよ．
입력
入力は以下の形式で標準入力から与えられる．
N K
A1 A2 … AN
출력
標準出力に，JOI 君が食べる飴の美味しさの合計の最大値を 1 行で出力せよ．
제한
2 ≦ K ≦ N ≦ 3 000．1 ≦ Ai ≦ 109(1 ≦ i ≦ N)．- 入力される値はすべて整数である．