Minimization

题意翻译

给定数组$A$ 和值$k$ ，你可以重排$A$ 中的元素，使得$\displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}|$ 最小。输出最小值。

题目描述

You've got array $ A $ , consisting of $ n $ integers and a positive integer $ k $ . Array $ A $ is indexed by integers from $ 1 $ to $ n $ . You need to permute the array elements so that value  became minimal possible. In particular, it is allowed not to change order of elements at all.

输入输出格式

输入格式

The first line contains two integers $ n,k $ ( $ 2<=n<=3·10^{5} $ , $ 1<=k<=min(5000,n-1) $ ). The second line contains $ n $ integers $ A[1],A[2],...,A[n] $ ( $ -10^{9}<=A[i]<=10^{9} $ ), separate by spaces — elements of the array $ A $ .

输出格式

Print the minimum possible value of the sum described in the statement.

输入输出样例

输入样例 #1

3 2
1 2 4

输出样例 #1

1

输入样例 #2

5 2
3 -5 3 -5 3

输出样例 #2

0

输入样例 #3

6 3
4 3 4 3 2 5

输出样例 #3

3

说明

In the first test one of the optimal permutations is $ 1 4 2 $ . In the second test the initial order is optimal. In the third test one of the optimal permutations is $ 2 3 4 4 3 5 $ .