Circular Barn Revisited#10587
The barn consists of a ring of rooms, numbered clockwise from to around the perimeter of the barn. Each room has doors connecting it to its two neighboring rooms, as well as a door leading to the exterior of the barn.
Farmer John wants exactly r_i cows to end up in room . To herd the cows into the barn in an orderly fashion, he plans to unlock exterior doors, allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to choose the exterior doors so that the cows collectively walk the minimum possible total distance after entering the barn. The cows may initially line up in any manner outside the unlocked doors, and this does not contribute to the total distance. Please determine the minimum total distance the cows need to walk if Farmer John chooses the optimal doors to unlock.
The first line contains two integers n~(3 \le n \le 100) and k~(1 \le k \le 7). The next lines each contain an integer r_i~(1 \le r_i \le 10^6), where r_i is the number of cows that must end up in room .
Print the minimum total distance the cows need to walk.
Farmer John can unlock doors and . cows enter through door and walk a total distance of to reach rooms , and . cows enter through door and walk a total distance of to reach rooms , and .
Example 1