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}