#1953
Minimization
NOI/NOI+/CTSCMinimization
题目描述
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

Input
The first line contains two integers n,k (2≤n≤3·105, 1≤k≤min(5000,n-1)).
The second line contains n integers A[1],A[2],...,A[n] (-109≤A[i]≤109), separate by spaces − elements of the array A.
Output
Print the minimum possible value of the sum described in the statement.
Examples
3 2
1 2 4
1
5 2
3 -5 3 -5 3
0
6 3
4 3 4 3 2 5
3
Note
In the first test one of the optimal permutations is 142.
In the second test the initial order is optimal.
In the third test one of the optimal permutations is 234435.