원형 축사

시간 제한2초메모리 제한512 MB

요약

원형 외양간에 바깥문 최대 k개를 열어 각 방까지 시계 방향으로 걷는 전체 거리를 최소화합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

현대 건축을 좋아하는 농부 John은 완벽한 원 모양으로 새 축사를 지었다. 축사 안에는 방 $n$ 개가 고리처럼 이어져 있고, 축사 둘레를 따라 시계 방향으로 $1$ 번부터 $n$ 번까지 번호가 붙어 있다 ( $3 \le n \le 1000$ ). 각 방에는 양옆 방으로 통하는 문이 하나씩 있고, 축사 바깥으로 나가는 문도 하나 있다.

John은 $i$ 번 방에 소가 정확히 $r_i$ 마리 있게 만들려고 한다 ( $1 \le r_i \le 1000000$ ). 소를 질서 있게 몰아넣으려고 바깥문을 최대 $k$ 개까지 열기로 했고 ( $1 \le k \le 7$ ), 소는 열린 문으로만 들어올 수 있다. 축사에 들어온 소는 자기 방에 닿을 때까지 시계 방향으로 방을 지나간다. 이웃한 두 방 사이를 한 번 지나가면 거리가 $1$ 늘어난다. 소는 열린 문 앞에 원하는 대로 미리 줄을 서도 되고, 줄을 서는 데는 거리가 들지 않는다.

문을 가장 잘 골랐을 때, 소가 축사에 들어온 뒤 걷는 거리의 합이 얼마나 작아지는지 구하라.

입력

첫째 줄에 $n$ 과 $k$ 가 주어진다. 이어지는 $n$ 개 줄에 $r_1$ 부터 $r_n$ 까지 한 줄에 하나씩 순서대로 주어진다.

출력

소가 걷는 거리의 합의 최솟값을 출력한다.

힌트

첫 번째 예제에서는 $2$ 번 문과 $5$ 번 문을 열면 된다. $2$ 번 문으로 소 $11$ 마리가 들어와 $2$ 번, $3$ 번, $4$ 번 방으로 가면서 거리 $8$ 을 걷고, $5$ 번 문으로 소 $10$ 마리가 들어와 $5$ 번, $6$ 번, $1$ 번 방으로 가면서 거리 $6$ 을 걷는다.

예제5

예제 1
입력
```
6 2
2
5
4
2
6
2
```
예상 출력
```
14
```
예제 2
입력
```
3 1
1
1
1
```
예상 출력
```
3
```
예제 3
입력
```
3 3
5
7
9
```
예상 출력
```
0
```
예제 4
입력
```
5 2
1
1000000
1
1
1
```
예상 출력
```
4
```
예제 5
입력
```
8 3
1
2
3
4
5
6
7
8
```
예상 출력
```
26
```