CSES - Datatähti Open 2021 - Programmers
  • Time limit: 1.00 s
  • Memory limit: 512 MB
A company employs $n$ programmers, who each have a skill level. Among them, it is desired to select $k$ pairs, where skill levels are close to each other.

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}$
Subtask 2 (21 points)
  • $2 \le n \le 2 \cdot 10^{5}$
  • $1 \le x_i \le 1000$
Subtask 3 (45 points)
  • $2 \le n \le 2 \cdot 10^{5}$
  • $1 \le x_i \le 10^{9}$