Circular Barn (Platinum)

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1 ... n around the perimeter of the barn. Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

Farmer John wants exactly r[i] cows to end up in room i. To herd the cows into the barn in an orderly fashion, he plans to unlock k 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 unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the k unlocked doors; this does not contribute to the total distance in question). Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.

Input

The first line contains n (3 ≤ n ≤ 1000) and k (1 ≤ k ≤ 7). Each of the remaining n lines contain r[1] ... r[n] (1 ≤ r[i] ≤ 10^6).

Output

Write out the minimum amount of distance the cows need to travel.

Examples

Note

Farmer John can unlock doors 2 and 5. 11 cows enter at door 2 and walk a total distance of 8 to get to rooms 2, 3 and 4. 10 cows enter at door 5 and walk a total distance of 6 to get to rooms 5, 6 and 1.