Farmer John has a round barn. The barn consists of a ring of n rooms, numbered 1…n around the perimeter (3≤n≤1,000). Each room has doors to two adjacent rooms and one door to the outside world.
The FD wants to place exactly ri cows in room i (1≤ri≤1,000,000). He plans to open k outer doors (1≤k≤7) through which the cows will enter the barn. Each cow then goes clockwise until it reaches the correct room. The FD wants to open the doors so that all the cows walk the shortest possible distance together. The cows can preliminarily gather in front of these unlocked doors as they see fit (these movements are not included in the total distance taken into account in the problem). Determine the minimum total distance that the cows will have to travel if the FD best chooses which k to open.
INPUT FORMAT:
The first input line contains n and k. The next n lines contain r1…rn.
INPUT FORMAT:
Print the minimum total distance traveled by the cows.
|
Enter |
Output |
|
6 2
2
5
4
2
6
2
|
14 |
The FD can open doors 2 and 5. 11 cows will enter doors 2 and travel a total distance of 8 to reach rooms 2,3,4. 10 cows will enter door 5 and travel a total distance of 6 to reach rooms 5,6,1.