P5929 [POI 1999 R3] 地图

一个人口统计办公室要绘制一张地图。

由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色 $k$，则 $A(k)$ 是相应的数，则有： - 在用颜色 $k$ 的区域中至少有一半的区域的人口不大于 $A(k)$； - 在用颜色 $k$ 的区域中至少有一半的区域的人口不小于 $A(k)$。 区域颜色误差是该区域的人口与 $A(k)$ 差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案，使得累计误差最小。

第一行有一个整数 $n$，表示区域数。 在第二行中的数 $m$ 表示颜色数。 在接下来的 $n$ 行中每行有一个非负整数，表示一个区域的人口。 人口都不超过 $2^{30}$。

输出一个整数，表示最小的累计误差。

对于 $100\%$ 的数据，$10 < n < 3000$，$2 \le m \le 10$。