두더지 잡기

잔디밭에 두더지굴 $n$개가 원형으로 놓여 있고, 각 굴에는 $1$번부터 $n$번까지 차례로 번호가 매겨져 있다. 원형이므로 $1$번과 $2$번, $2$번과 $3$번, $\dots$, $n$번과 $1$번 굴이 서로 인접하다.

지금 $i$번 굴에는 두더지가 $a_i$마리 있다. 모형 권총으로 $i$번 굴을 쏘면 다음 일이 동시에 일어난다.

• $i$번 굴에 있던 두더지는 모두 겁을 먹고 굴 밖으로 탈출한다. (이렇게 굴을 탈출한 두더지가 '쫓아낸' 두더지로 집계된다.)
• $i$번 굴과 인접한 두 굴에 있던 두더지도 겁을 먹어, $i$번 굴이 아닌 반대쪽 이웃 굴로 달아난다. 즉 $i-1$번 굴의 두더지는 $i-2$번 굴로, $i+1$번 굴의 두더지는 $i+2$번 굴로 이동한다.

예를 들어 $10$번 굴을 쏘면, $10$번 굴의 두더지는 모두 탈출하고 $9$번 굴의 두더지는 $8$번 굴로, $11$번 굴의 두더지는 $12$번 굴로 이동한다.

권총을 최대 $k$번 쏠 수 있을 때, 굴 밖으로 탈출시킬 수 있는 두더지 수의 최댓값을 구하여라.

첫째 줄에 두더지굴의 수 $n$과 권총을 쏠 수 있는 최대 횟수 $k$가 주어진다. ($5 \le n \le 2000$, $1 \le k \le n$)

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. $a_i$는 $i$번 굴에 있는 두더지의 수이다. ($0 \le a_i \le 10^6$)

권총을 최대 $k$번 사용했을 때 굴 밖으로 탈출시킬 수 있는 두더지 수의 최댓값을 한 줄에 출력한다.

굴의 상태가 $[6, 1, 5, 3, 4]$라고 하자. (왼쪽부터 차례로 $1$번 굴이다.)

먼저 $1$번 굴을 쏘면 그 굴의 두더지 $6$마리가 탈출한다. 이때 $1$번 굴의 이웃인 $5$번 굴($n$번 굴)의 두더지는 $4$번 굴로, $2$번 굴의 두더지는 $3$번 굴로 이동하여 상태는 $[0, 0, 6, 7, 0]$이 된다.

다음으로 $4$번 굴을 쏘면 그 굴에 모인 두더지 $7$마리가 탈출한다. 두 번의 사격으로 모두 $6 + 7 = 13$마리를 쫓아낼 수 있다.