You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $n$ 个点的完全图，第 $i$ 个点上写有数字 $a_i$，点 $i$ 和点 $j$ 之间的边的边权为 $|a_i-a_j|$。

定义一种 $m$ 匹配的权值如下：从图中选出 $2m$ 个点和 $m$ 条边，每一条选中的边恰好连结两个选中的点，每一个选中的点恰好被一条选中的边连结，则权值即为所有选中的边的边权和。

求所有 $m$ 匹配的权值的最小值。

输入格式

从文件 $halcyon.in$ 中读入数据。

第一行两个正整数 $n,m$。

第二行n个正整数 $a_1,a_2,...,a_n$。

输出格式

输出到文件 $halcyon.out$ 中。

一行一个非负整数表示答案。

样例 1 输入

4 1
2 4 7 3

样例 1 输出

1

样例 2 输入

8 3
9 2 3 12 11 7 6 5

样例 2 输出

3

样例 3

见右侧文件下的 $halcyon3.in$ 与 $halcyon3.ans$。

数据范围与提示

对于所有测试数据，保证 $1≤2m≤n≤5000，1≤a_i≤10^9$。

每个测试点的具体限制见下表：