No.615 集合に分けよう

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 150
作問者 : ミドリムシ+ミドリムシ+ / テスター : はむこはむこ
13 ProblemId : 2022 / 出題時の順位表
 この問題は、Advent Calendar Contest 2017の15日目の問題です。

問題文

$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 \leq K \leq N \leq 5 \times 10^4$
$0 \leq a_i \leq 10^{12}$

出力

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

注意

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

サンプル

サンプル1
入力
5 2
1 10 11 2 9
出力
3

集合{$11, 9, 10$}と集合{$2, 1$}に分けると、
{$2, 1$}の大きさは$2 - 1 = 1$
{$11, 9, 10$}の大きさは$11 - 9 = 2$
となるので、分けた後の集合の大きさの総和は$3$になり、これが最小値である。

サンプル2
入力
4 2
0 7 3 13
出力
7

集合{$0, 7, 3$}と集合{$13$}に分けることで、最小値を達成できる。

サンプル3
入力
3 3
1 10 100
出力
0

集合{$1$}と集合{$10$}と集合{$100$}に分けることで、最小値を達成できる。

サンプル4
入力
3 1
0 0 1000000000000
出力
1000000000000

集合{$0, 0, 1000000000000$}に分けることしか出来ず、この時が最小値になる。
オーバーフローに注意。

サンプル5
入力
10 3
1 12 19 23 28 3 32 36 41 7
出力
28

集合{$12$}と集合{$28, 23, 41, 19, 32, 36$}と集合{$3, 1, 7$}に分けることで、最小値を達成できる。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。