Circular Barn

Farmer John likes contemporary architecture, so his new barn is a perfect circle. Inside, the barn is a ring of $n$ rooms, numbered $1$ through $n$ clockwise around the perimeter ($3 \le n \le 1000$). Each room has a door to each of its two neighbouring rooms, and one more door that opens to the outside.

Farmer John wants exactly $r_i$ cows to end up in room $i$ ($1 \le r_i \le 1000000$). To herd the cows in without a stampede he unlocks at most $k$ of the exterior doors ($1 \le k \le 7$), and a cow may enter only through an unlocked door. Once inside, a cow walks clockwise from room to room until she reaches her own room. Walking between two neighbouring rooms adds $1$ to the distance. The cows may line up outside the unlocked doors however they like, and lining up costs no distance.

Find the smallest total distance the cows walk after entering the barn, over the best choice of doors.

The first line contains $n$ and $k$. Each of the next $n$ lines contains one value, $r_1$ through $r_n$ in order.

Print the minimum total distance the cows walk.

In the first example Farmer John unlocks doors $2$ and $5$. The $11$ cows entering at door $2$ walk a total distance of $8$ to reach rooms $2$, $3$ and $4$. The $10$ cows entering at door $5$ walk a total distance of $6$ to reach rooms $5$, $6$ and $1$.