Minimizing Circular Barn Walking Distance

Farmer John, an avid admirer of modern architecture, has built a circular barn with n rooms arranged in a circle (3 ≤ n ≤ 1000). The rooms are numbered in clockwise order from 1 to n. Each room has doors to its two adjacent rooms and one door leading directly outside.

Farmer John wants exactly r_i cows (1 ≤ r_i ≤ 10⁶) to be in room i. To control the order in which the cows enter, he plans to unlock exactly k external doors (1 ≤ k ≤ 7). Each cow will enter through one of the unlocked doors and then walk strictly clockwise until she reaches her assigned room. The distance a cow walks is measured only from the barn entry (i.e. after entering from the door) until reaching her destination.

Your task is to choose which k doors to unlock and assign entry points for the cows so that the total walking distance of all cows is minimized. Note that you are free to decide from which unlocked door each cow enters.

The walking distance for a contiguous block of rooms served by a particular door is calculated as follows: if the door is placed at the first room of the block, cows destined for that room walk 0, for the next room they walk 1 unit, for the next room 2 units, and so on. The goal is to minimize the aggregated distance over all rooms.

Hint: This problem can be solved by considering all possible rotations of the circular barn into a linear arrangement and then using dynamic programming to partition the sequence into k segments.

inputFormat

The first line contains two integers n and k separated by a space.

The next n lines each contain a single integer r_i, representing the number of cows required in room i (in clockwise order).

Example:

3 1
1
2
3

outputFormat

Output a single integer indicating the minimum total walking distance of all cows.

Example:

5

sample

3 1
1
2
3

5