사탕 2

문제

책상 위에 $N$ 개의 사탕이 가로로 한 줄로 놓여 있으며, 왼쪽부터 순서대로 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 사탕 $i$ ($1 \le i \le N$) 의 맛있음은 $A_{i}$ 이다.

JOI 군은 $N$ 개의 사탕 중 몇 개를 골라서 먹기로 했다.

다만, 사탕을 너무 많이 먹지 않기 위해, 연속한 $K$ 개의 사탕 중에서는 많아야 $2$ 개만 먹도록 한다. 즉, 어떤 $j$ ($1 \le j \le N - K + 1$) 에 대해서도, 사탕 $j$ 부터 사탕 $j + K - 1$ 까지의 연속한 $K$ 개의 사탕 중 먹는 사탕의 개수는 $2$ 개 이하여야 한다.

이 조건 하에서, JOI 군은 먹는 사탕의 맛있음의 합을 가능한 한 크게 하고 싶다.

$N$ 개의 사탕의 맛있음과 $K$ 가 주어졌을 때, JOI 군이 먹는 사탕의 맛있음의 합의 최댓값을 구하는 프로그램을 작성하시오.

제한

• $2 \le K \le N \le 3\,000$.
• $1 \le A_{i} \le 10^{9}$ ($1 \le i \le N$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($4$ 점) $N \le 20$.
2. ($19$ 점) $K \le 10$.
3. ($47$ 점) $N \le 300$.
4. ($30$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $K$
$A_{1}$ $A_{2}$ $\dots$ $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

이 예제는 모든 서브태스크의 제약을 만족한다.