問題文

$N$個の整数があり、それぞれ$a_1,a_2,...a_n$である。
この$N$個の整数を$K$個の集合に分けたい。
ここで、集合の大きさを その集合に含まれる要素の最大値と最小値の差 と定義する。
例えば、集合{$1,7,4$}は最大値が$7$で最小値が$1$なので、この集合の大きさは$7-1=6$になる。
上手く分けて、分けた後の集合の大きさの総和を最小化したい。
分けた後の集合の大きさの総和の最小値を求めなさい。

ただし、$p$個の整数を$q$個の集合$x_1,x_2...x_q$に分ける とは、次の条件を満たしているということである。
・集合$x_1,x_2,...x_q$の要素を全て合わせた要素数$p$の集合を 集合$X$ と呼ぶことにすると、集合$X$の各要素と$p$個の各整数は同じ数同士を対応させると1対1対応する。

入力

$N$ $K$
$a_1$ $a_2$ ... $a_n$

$1\le K\le N\le 5\times {10}^4$
$0\le a_i\le {10}^{12}$

出力

答えを出力せよ。 末尾に改行を入れること。

注意

この問題で扱う数値が$2^{31}$以上になる可能性がある。

サンプル

5 2
1 10 11 2 9

3

4 2
0 7 3 13

7

3 3
1 10 100

0

3 1
0 0 1000000000000

1000000000000

10 3
1 12 19 23 28 3 32 36 41 7

28