Circular Barn Revisited

Farmer John's circular barn consists of \(n\) rooms arranged in a ring. Each room \(i\) (numbered \(1 \ldots n\) clockwise) has an exterior door and doors connecting it to its two neighbouring rooms. Farmer John wants exactly \(r_i\) cows to occupy room \(i\). To control the herd, he will unlock exactly \(k\) of the exterior doors. The cows can line up arbitrarily at these unlocked doors. After entering through an unlocked door, each cow walks clockwise from room to room until she finds a room that still needs cows. The distance a cow walks is counted as the number of rooms she passes (with the room she enters counting as distance \(0\)).

Your task is to choose which \(k\) doors to unlock so that the total walking distance of all cows is minimized. Output this minimum total distance.

inputFormat

The first line contains two integers \(n\) and \(k\) (where \(3 \le n \le 100\) and \(1 \le k \le 7\)). The next \(n\) lines each contain an integer \(r_i\) (\(1 \le r_i \le 1,000,000\)), which indicates the number of cows that must ultimately be in room \(i\). The rooms are given in clockwise order.

outputFormat

Output a single integer: the minimum total distance the cows need to walk after entering the barn through the selected \(k\) unlocked doors.

sample

3 1
1
2
3

5