There are n houses on a street, numbered 1,2,\dots,n. The distance of houses a and b is |a-b|. You know the number of children in each house.

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.