题目描述

给定一个数组 A，含有 n 个整数，再给出一个整数 K，问 n 个整数需要怎样排列才能使下式：
n-k
Σ | \(A_i\)-\(A_{i + k}\) |
i=1
的值最小。

输入格式

第一行包括两个整数 n, k。
第二行包括 n 个整数 \(A_1\), \(A_2\), …, \(A_n\)。

输出格式

输出最小值。

样例1

输入

3 2
1 2 4

输出

1

样例1

输入

5 2
3 -5 3 -5 3

输出

0

样例1

输入

6 3
4 3 4 3 2 5

输出

3

数据范围

对于30%的数据，2 ≤ n ≤ 50, 1 ≤ k ≤ min(50, n - 1)， - 10^9 ≤ \(A_i\) ≤ 10^9
对于100%的数据，2 ≤ n ≤ 3 * 10^5, 1 ≤ k ≤ min(5000, n - 1)， - 10^9 ≤ \(A_i\) ≤ 10^9

限制

1s

样例解释

样例1：最佳排列1 4 2
样例2：初始最优
样例3：最佳排列2 3 4 4 3 5

来源

Codeforces571B
CWOI新高二专题测试十三