소 사방치기

소들이 어린 시절로 돌아가 사람의 사방치기와 비슷한 놀이를 하고 있다. 이 놀이는 잔디밭에 분필로 그린 한 줄의 정사각형 칸 $N$개를 사용하며, 칸에는 $1 \dots N$의 번호가 매겨져 있다. 여기서 $3 \le N \le 250000$이다.

좋은 놀이가 다 그렇듯 이 사방치기에도 상금이 걸려 있다. $i$번 칸에는 정수 상금 $V_i$가 적혀 있으며, $-2000000000 \le V_i \le 2000000000$이다. 소들은 누가 가장 많은 돈을 버는지 겨룬다.

규칙은 다음과 같다.

• 소는 $1$번 칸 바로 앞에 있는 $0$번 칸에서 출발한다. $0$번 칸에는 상금이 없다.
• 소는 $N$번 칸 방향으로 (비어 있어도 되는) 점프를 이어서 한다. 새로 착지하는 칸은 직전 칸으로부터 최대 $K$칸 앞이어야 하며, $2 \le K \le N$이다. (예를 들어 $K = 2$일 때 $1$번 칸에서는 앞으로 $2$번 또는 $3$번 칸으로 점프할 수 있다.)
• 소는 원하는 순간에 방향을 돌려 $0$번 칸 쪽으로 되돌아가는 점프를 하며, $0$번 칸에 도착하면 멈춘다. 돌아올 때에도 한 번에 최대 $K$칸이라는 제한이 똑같이 적용되고, 다음 두 제약이 추가된다.
  1. 되돌아올 때에는 나아갈 때 밟았던 칸에는 착지할 수 없다(단 $0$번 칸은 예외).
  2. $0$번 칸을 제외하고, 되돌아올 때 착지하는 모든 칸은 나아갈 때 착지했던 어떤 칸의 바로 앞 칸이어야 한다(즉 그 칸의 번호보다 정확히 $1$ 작은 칸). 도중에 착지할 수 있는 복귀 칸들을 건너뛰는 더 큰 점프를 해도 된다.

소는 착지한 모든 칸의 상금의 합만큼 돈을 번다. 소가 벌 수 있는 최대 금액을 구하여라.

예시로 $K = 3$인 여섯 칸짜리 코스를 생각해 보자.

칸 번호:   0      1      2      3      4      5      6
         +---+  +---+  +---+  +---+  +---+  +---+  +---+
         |///|--|   |--|   |--|   |--|   |--|   |--|   |
         +---+  +---+  +---+  +---+  +---+  +---+  +---+
상금:      -      0      1      2     -3      4      5

최적의 점프 순서 하나는(대괄호 안은 그 칸에서 얻는 상금) $1[0],\ 3[2],\ 6[5],\ 5[4],\ 2[1],\ 0[0]$이며, 합계는 $0 + 2 + 5 + 4 + 1 + 0 = 12$이다. 반대로 $0, 1, 2, 3, \dots$처럼 앞으로만 나아간 소는 되돌아올 수 없다. 되돌아올 때 착지할 수 있는 칸(나아갈 때 밟은 칸의 바로 앞 칸)이 모두 이미 밟은 칸이기 때문이다.

참고: 소는 아무 점프도 하지 않기로 선택할 수도 있으며, 이때 얻는 금액은 $0$이다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• $2 \dots N+1$번째 줄: $i+1$번째 줄에는 정수 $V_i$ 하나가 주어진다.

• 한 줄에 정수 하나: 소가 벌 수 있는 최대 금액.