Circular Barn

Time limit2sMemory limit512 MB

Summary

Choose up to k outer doors on a ring of n rooms so the total clockwise walking distance to every cow room is minimized.

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

Problem

Farmer John likes contemporary architecture, so his new barn is a perfect circle. Inside, the barn is a ring of $n$ rooms, numbered $1$ through $n$ clockwise around the perimeter ( $3 \le n \le 1000$ ). Each room has a door to each of its two neighbouring rooms, and one more door that opens to the outside.

Farmer John wants exactly $r_i$ cows to end up in room $i$ ( $1 \le r_i \le 1000000$ ). To herd the cows in without a stampede he unlocks at most $k$ of the exterior doors ( $1 \le k \le 7$ ), and a cow may enter only through an unlocked door. Once inside, a cow walks clockwise from room to room until she reaches her own room. Walking between two neighbouring rooms adds $1$ to the distance. The cows may line up outside the unlocked doors however they like, and lining up costs no distance.

Find the smallest total distance the cows walk after entering the barn, over the best choice of doors.

Input

The first line contains $n$ and $k$ . 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.

Hint

In the first example Farmer John unlocks doors $2$ and $5$ . The $11$ cows entering at door $2$ walk a total distance of $8$ to reach rooms $2$ , $3$ and $4$ . The $10$ cows entering at door $5$ walk a total distance of $6$ to reach rooms $5$ , $6$ and $1$ .

Examples5

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
5
7
9
```
Expected output
```
0
```
Example 4
Input
```
5 2
1
1000000
1
1
1
```
Expected output
```
4
```
Example 5
Input
```
8 3
1
2
3
4
5
6
7
8
```
Expected output
```
26
```