你有数组 A,由 n 个整数和一个正整数 k 组成。数组 A 由 1 到 n 之间的整数索引。
您需要排列数组元素,以便值
$$\sum_{i=1}^{n-k}|A[i]-A[i+k]|$$
输入
第一行包含两个整数 n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1))。
第二行包含 n 个整数 A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109),用空格分隔 — 数组 A 的元素。
输出
打印语句中描述的总和的最小可能值。
示例
输入 #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
注意
在第一个测试中,最佳排列之一是 1 4 2。
在第二个测试中,初始顺序是最佳的。
在第三个测试中,最佳排列之一是 2 3 4 4 3 5。