Problem Description

As a fan of modern architecture, Farmer John built a new circular barn. Inside the barn, there are $n$ rooms arranged in a ring ($3 \leq n \leq 1000$), numbered $1 \ldots n$ in clockwise order. Each room has doors to its left and right neighboring rooms, and also a door leading outside.

FJ wants room $i$ to contain exactly $r_i$ cows ($1 \le r_i \le {10}^6$). To let the cows enter the barn in an orderly way, he plans to unlock $k$ doors from the outside into the barn ($1 \le k \le 7$). Then, each cow walks clockwise until it reaches its destination. FJ's goal is to minimize the total distance walked by all cows (the entry door for each cow can be chosen freely; the distance only counts walking after entering the barn). Please find this minimum total distance.

Input Format

The first line contains two integers $n, k$.

The next $n$ lines each contain an integer $r_i$ on line $i$.

Output Format

Output the minimum total distance walked by all cows.

6 2
2
5
4
2
6
2

14

Hint

FJ opens doors $2$ and $5$. $11$ cows enter through door $2$ and go to rooms $2, 3, 4$, with a total distance of $8$. $10$ cows enter through door $5$ and go to rooms $5, 6, 1$, with a total distance of $6$.

Translated by ChatGPT 5