다시 찾은 원형 축사

농부 존의 원형 축사는 방 $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$다.