Circular Barn Revisited

Time limit2sMemory limit512 MB

Summary

Farmer John opens k doors on a ring of n rooms so cows walking clockwise to their assigned rooms travel the smallest total distance.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum, Intervals
Solved: No attempts yet

Problem

Farmer John's circular barn is a ring of $n$ rooms, numbered $1$ through $n$ clockwise around the perimeter. Each room has inner doors to its two neighbours and one door to the outside.

Farmer John wants exactly $r_i$ cows to end up in room $i$ . To herd them in an orderly way he unlocks only $k$ of the exterior doors, and every cow enters through one of those. Once inside, a cow walks clockwise until it reaches its room, so a cow that enters at the door of room $d$ and settles in room $i$ walks a distance of $(i - d) \bmod n$ . The cows may line up outside the $k$ unlocked doors however they like, and the lining up does not count toward the distance.

Choose the $k$ doors that minimise the total distance the cows walk inside the barn, then report that total.

$3 \le n \le 100$ , $1 \le k \le 7$ , $k \le n$ , and $1 \le r_i \le 10^6$ .

Input

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

Output

Print the minimum total distance the cows walk, on one line.

Note

In the first example Farmer John unlocks the doors of rooms $2$ and $5$ . Eleven cows enter at door $2$ and settle in rooms $2$ , $3$ and $4$ , walking $8$ in total. Ten cows enter at door $5$ and settle in rooms $5$ , $6$ and $1$ , walking $6$ in total. The two values add up to $14$ .

Examples3

Example 1
Input
```
6 2
2
5
4
2
6
2
```
Expected output
```
14
```
Example 2
Input
```
3 1
1
1
1
```
Expected output
```
3
```
Example 3
Input
```
3 3
1000000
1000000
1000000
```
Expected output
```
0
```