다시 찾은 원형 축사

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

요약

원형 외양간의 방 n개 중 문 k개를 열어 소들이 시계 방향으로 정해진 마릿수만큼 이동할 때 전체 이동 거리를 최소화합니다.

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

문제

농부 존의 원형 축사는 방 $n$ 개가 고리 모양으로 이어져 있다. 방에는 시계 방향으로 $1$ 번부터 $n$ 번까지 번호가 붙어 있고, 각 방은 양옆 두 방과 안쪽 문으로 이어져 있으며 축사 바깥으로 나가는 문도 하나씩 있다.

존은 $i$ 번 방에 소가 정확히 $r_i$ 마리 들어가기를 원한다. 소를 질서 있게 몰아넣으려고 바깥문 중 $k$ 개만 열어 두고, 소는 열린 문으로만 축사에 들어온다. 안으로 들어온 소는 자기 방에 닿을 때까지 시계 방향으로만 걷는다. $d$ 번 방의 문으로 들어와 $i$ 번 방에 자리 잡은 소가 걷는 거리는 $(i - d) \bmod n$ 이다. 소가 축사 밖에서 열린 문 $k$ 개 앞에 어떻게 줄을 서든 상관없고, 줄을 서면서 움직인 거리는 세지 않는다.

축사 안에서 소가 걷는 거리의 합이 최소가 되도록 열 문 $k$ 개를 고를 때, 그 거리의 합을 구하라.

$3 \le n \le 100$ , $1 \le k \le 7$ , $k \le n$ , $1 \le r_i \le 10^6$ 이다.

입력

첫째 줄에 $n$ 과 $k$ 가 공백을 사이에 두고 주어진다. 이어지는 $n$ 개의 줄에 $r_1$ 부터 $r_n$ 까지 한 줄에 하나씩 주어진다.

출력

소가 걸어야 하는 거리의 합의 최솟값을 한 줄에 출력한다.

노트

첫 번째 예제에서는 $2$ 번 문과 $5$ 번 문을 연다. $2$ 번 문으로 소 $11$ 마리가 들어와 $2$ 번, $3$ 번, $4$ 번 방에 자리 잡으며 모두 합쳐 $8$ 만큼 걷는다. $5$ 번 문으로 소 $10$ 마리가 들어와 $5$ 번, $6$ 번, $1$ 번 방에 자리 잡으며 모두 합쳐 $6$ 만큼 걷는다. 두 값을 더하면 $14$ 다.

예제3

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