**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to establish $k$ schools in such a way that each school is in some house. Then, each child goes to the nearest school. What is the minimum total walking distance of the children if you act optimally?

**Input**

The first input line has two integers $n$ and $k$: the number of houses and the number of schools. The houses are numbered $1,2\dots,n$.

After this, there are $n$ integers $c_1,c_2,\dots,c_n$: the number of children in each house.

**Output**

Print the minimum total distance.

**Constraints**

- $1 \le k \le n \le 3000$

- $1 \le c_i \le 10^9$

**Example**

Input:

`6 2`

2 7 1 4 6 4

Output:

`11`

Explanation: Houses 2 and 5 will have schools.