题目描述

某公司基地搬迁后新规划了一条班车路线，沿途经过 N 个小区，需要从中选择 M 个小区作为上车点。小区的位置可以表示为一维坐标点 x1, x2, ..., xN。一个小区到上车点的距离是两点坐标差的绝对值。

目标是选取 M 个上车点，使得所有小区到最近上车点的距离总和最小，并返回这个最小值。

输入描述

• 第一行两个整数 N, M，分别表示小区数量和上车点数量（1 < M <= N <= 50）。
• 第二行 N 个不重复的整数 x1, x2, ..., xN，表示小区的位置（1 <= xi <= 1000000）。

题目内容

某公司基地搬迁到新地点之后，新规划了一条班车路线，在这条路线上会经过 $N$ 个小区，计划在这些小区中挑选出 $M$ 个作为上车点，小区的位置可以用一维坐标上的点来表示，小区到上车点的距离为两个坐标点差值的绝对值。现在给定 $N$ 个小区的位置，即一维坐标上的整数点：$x1、x2、...、xN$ ，请计算选取 $M$ 上车点后，使得所有小区到最近上车点的距离总和尽可能小，并返回这个最小值。当该小区被作为上车点，该小区到上车点的距离为 $0$ 。

输入描述

第一行有两个整数，用空格隔开：$N$ $M$ ，$1<M<=N<= 50$

第二行有 $N$ 个没有重复的整数，用空格隔开，表示 $N$ 个小区的位置，$1<=xi<= 1000000$

输出描述

一个整数，表示所有小区到上车点的总和的最小值

样例1

输入

5 2
1 2 3 6 7

输出

3

说明

将上车点设置在 $2、6$ 这两个小区，可以使得所有小区到上车点的总距离最小为 $3$ 。

样例2

输入

10 5
1 2 3 6 7 11 22 44 50

输出

9

说明

将上车点设置在 $2、9、22、44、50$ 这 $5$ 个小区时，使得所有小区到上车点的总距离最小为 $9$ 。