- Time limit: 1.00 s
- Memory limit: 512 MB
When a pair of programmers with skill levels $a$ and $b$ is selected, a cost of $|a-b|$ is incurred. The total cost is the sum of this among all selected pairs.
Find the smallest possible total cost.
Input
The first line of input contains two integers $n$ and $k$: the number of programmers and the desired number of pairs. It holds that $1 \leq k \leq n/2$.
The next line contains $n$ integers $x_1,x_2,\dots,x_n$ representing the skill levels of each programmer.
Output
Print one integer: the smallest possible total cost.
Example
Input:
8 3
3 1 2 7 9 3 4 7
Output:
1
Explanation: It is possible to choose pairs with skill levels $(1,2)$, $(3,3)$ and $(7,7)$.
Subtask 1 (34 points)
- $2 \le n \le 2000$
- $1 \le x_i \le 10^{9}$
- $2 \le n \le 2 \cdot 10^{5}$
- $1 \le x_i \le 1000$
- $2 \le n \le 2 \cdot 10^{5}$
- $1 \le x_i \le 10^{9}$