AT_tkppc2016_f.NPCの家 (NPC's House)

对于AtCoder上的这个问题中描述的NPC的家问题，joisinoお姉ちゃん已经确认了 NPC 的移动，现在她被委托安排 NPC 的家。在一个无限延伸的直线上，有 $ N $ 个NPC站立。并要在这条直线上设置 $ M $ 个NPC的家。然后，每个NPC将返回到最近的家。

在这个游戏中，为了追求现实感，必须将NPC的家放置在使每个 NPC 返回家的距离之和最小化的位置。

为了高效地进行这项任务，joisino お姉ちゃん 决定编写一个程序，以确定使每个NPC返回家的最小距离之和。

配分

此问题有部分分。

• 数据集1满足$N\leq300，M\leq300$，解决将获得10分。
• 数据集2没有额外的限制，解决将获得110分。

输出

输出使每个NPC返回家的最小距离之和。

---

示例输入1

5 2
-3
-1
0
2
5

示例输出1

6

• 例如，将家放置在位置$-1，2$，NPC1、2和3返回到位置$-1$的家，而NPC4和5返回到位置$2$的家。 因此，每个NPC返回家的距离之和为$2+0+1+0+3=6$。
• 没有其他配置可以使每个NPC返回家的距离之和更小，因此答案为6。

---

示例输入2

10 3
-3
12
-92
-45
-15
27
14
94
-39
75

示例输出2

131