문제 설명

책상 위에 $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 ... 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

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