원형 축사

현대 건축을 좋아하는 농부 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$을 걷는다.