题目描述

There are $N$ villagers (including the village chief) living in Number Village. Interestingly, all of their houses lie on a straight line. The house of the $i$-th villager ($0\leq i<N$) lies exactly $a_i$ kilometers to the east of the village chief's house. (For simplicity, the $0$-th villager is the village chief, so $a_0=0$.)

Recently, a tournament is going to be held in Number Village, in which everyone in the village will participate.

For the convenience of villagers, the organizer plans to build $K$ stadiums. The stadium can be built anywhere in the village, even at the same place as any villager's house.

However, the organizer wants the traffic cost to be minimized. The traffic cost is defined by $\sum_{i=0}^{N-1} \min_{j=0}^{K-1} D(a_i, s_j)$, where $D(a_i, s_j)$ is the distance between the $i$-th villager's house and the $j$-th stadium.

Your task is to calculate the minimal traffic cost (rounded down to the nearest integer), given $N, K$ and $a_i$.

输入格式

The first line contains two positive integers $N,K$ ($K\leq N\leq 3\times 10^ 5$).

The second line contains $N$ non-negative integers $a_0,a_1,\cdots,a_{N-1}$ ($0=a_0<a_1<\cdots<a_{N-1}\leq 10^ 9$).

输出格式

Print a single integer $\text{---}$ the minimal traffic cost rounded down to the nearest integer.

5 2
0 4 7 9 10

7

9 3
0 1 10 11 20 21 22 30 32

23