← 返回题目列表

Codeforces · 571/B

B. 最小化

中文机器翻译题面 查看原题

你有数组 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。