CF571B.Minimization

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.

你有一个包含 $ n $ 个整数的数组 $ A $ 和一个正整数 $ k $。数组 $ A $ 的下标范围为 $ 1 $ 到 $ n $。

你需要对数组元素进行重排（即构造一个排列），使得如下表达式的值达到最小可能值：

特别地，允许完全不改变元素的原有顺序（即恒等排列）。

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.

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 3 \cdot 10^5$，$1 \leq k \leq \min(5000, n - 1)$）。

第二行包含 $n$ 个整数 $A[1],\ A[2],\ \dots,\ A[n]$（$-10^9 \leq A[i] \leq 10^9$），以空格分隔——即数组 $A$ 的元素。

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

输出题目描述中所述和的最小可能值。

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.

在第一个测试用例中，一个最优排列是 1 4 2。

在第二个测试用例中，初始顺序即为最优。

在第三个测试用例中，一个最优排列是 2 3 4 4 3 5。