시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB125393533.333%

문제

机の上に 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).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
14

N ≦ 20

219

K ≦ 10

347

N ≦ 300

430

追加の制約はない.

예제 입력 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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.