J. Jalisco's Hydration Stations
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Etienne and Christian are organizing a Sunday event along Avenida Vallarta, modeled as a straight line. Participant $$$i$$$ waits at coordinate $$$x_i$$$.

They must place exactly $$$k$$$ hydration stations. Each station may be placed at any real coordinate, and multiple stations may be placed at the same coordinate. After the stations are placed, each participant walks to a station minimizing the absolute distance from their position. If several stations are equally near, choosing any of them gives the same walking distance.

Find the minimum possible sum of the walking distances of all participants.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100000$$$, $$$k \le 25$$$).

The second line contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$0 \le x_1 \le x_2 \le \cdots \le x_n \le 10^9$$$). Equal coordinates are allowed.

Output

Print one integer: the minimum possible total walking distance.

Although station coordinates may be real numbers, an optimal solution can place every station at a participant coordinate, so the answer is an integer. The answer fits in a signed 64-bit integer but may exceed the 32-bit range.

Example
Input
6 3
0 2 3 10 11 20
Output
4
Note

In the sample, stations can be placed at coordinates $$$2$$$, $$$10$$$, and $$$20$$$. The walking distances are $$$2,0,1,0,1,0$$$, for a total of $$$4$$$.

Requiring exactly $$$k$$$ stations never increases the optimum: any redundant station may be placed at the same coordinate as another station.