페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5857
서브태스크

사탕2 (Candies 2) 2초 1024MB

문제

책상 위에 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가 먹는 사탕의 맛의 합계의 최대치를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

N K

A_1 A_2 … A_N

[제한]

2 \le K \le N \le 3\,000

1 \le A_i \le 10^9 (1 \le i \le N)

입력된 모든 값은 정수이다.


출력

표준 출력에 JOI가 먹는 사탕의 맛의 합계의 최대치를 1 행으로 출력하라.


부분문제

번호 점수 조건
#14점

N ≤ 20

#219점

K ≤ 10

#347점

N ≤ 300

#430점

추가 제약은 없다


예제1

입력
54
13243
출력
8

JOI 당신이 사탕 1 , 사탕 4 , 사탕 5 를 먹을 때, 맛의 합계는 8 이 된다.

어떤 연속 4 개의 사탕에 대해서도 먹는 사탕의 개수가 2 개 이하인 것 같은 먹는 방법 중, 맛의 합계가 9 이상인 것 같은 것은 존재하지 않기 때문에, 8 을 출력한다.

이 입력 예제는 모든 작은 문제의 제약 조건을 충족합니다.


예제2

입력
63
371564
출력
21

JOI 너가 사탕 1 , 사탕 2 , 사탕 4 , 사탕 5 를 먹을 때, 맛의 합은 21 이 된다.

3 개의 연속 사탕에 대해 먹는 사탕의 개수가 2 개 이하인 먹는 방법 중 맛의 합이 22 이상인 것은 존재하지 않기 때문에 21 을 출력한다.

이 입력 예제는 모든 작은 문제의 제약 조건을 충족합니다.


예제3

입력
52
33221
출력
11

예제4

입력
125
864814169716638377926889183891468826217138351891972397504371916678159995435478604181254225760822841688502728
출력
4427122428

출처

JOI 2022 예선2

역링크