AT_s8pc_4_b.Buildings are Colorful!

有一排建筑物，高度分别为 $a_1, a_2, a_3, \ldots, a_N$，你的任务是选择其中 $K$ 座建筑物，以尽可能小的费用使高桥君能够从左看到这些建筑物，费用定义为建筑物的高度差。请寻找这个最小的费用。

输入为一行，包含 $N, K, a_1, a_2, \ldots, a_N$。

• $N$ 表示建筑物总数。
• $K$ 为需要选择的建筑物数量。
• $a_i$ 表示第 $i$ 座建筑物的高度。

输出一个整数，表示选择 $K$ 座建筑物所需的最小费用。输出结束换行。

• $1 \le K \le N \le 15$
• $1 \le a_i \le 10^9$

得分

• 小任务 1 [120 分]: $N = K$
• 小任务 2 [90 分]: $N \le 5$，且 $a_i \le 7$
• 小任务 3 [140 分]: 没有额外限制。

示例说明

示例 1

如果建筑物高度依次为 $3949, 3950, 3951, 3952, 3953$，可以选择全部建筑物，这时不需要额外费用来满足条件。

示例 2

当建筑物的高度为 $7, 8, 2, 9, 4$ 时，只需花费 $7$ 的费用就可以满足目标需求。

本翻译由 AI 自动生成