238. [POI 1999] 地图着色

【题目描述】

在 $Byteland$ 新的行政划分以后，制图工作室需要制作国家新的统计地图。因为技术上的原因，仅有很少的颜色能够被使用。地图上有着相同或者相似的人口（居民数）的地区被着为相同的颜色。对于给定的颜色 $k$，让 $A_k$ 为数字，意思为：

   至少有一半颜色为 $k$ 的地区人口不大于 $A_k$。

   至少有一半颜色为 $k$ 的地区人口不少于 $A_k$。

地区的着色误差是指 $A_k$ 与地区人口之间的差额的绝对值，累积误差是指所有地区的着色误差之和。我们要寻找一种地图的最佳着色方案（即最小的累积误差）。

【输入格式】

第一行一个正整数 $n$，表示 $Byteland$ 的地区数。

第二行一个正整数 $m$，表示用于着色的颜色数。

在接下来的 $n$ 行中的每行有一个非负的整数表示某一地区的人口数 $p_i$。

【输出格式】

输出一个整数，表示能够完成地图最佳着色的最小累积误差。

【样例输入1】

11
3
21
14
6
18
10
2
15
12
3
2
2

【样例输出1】

15

【样例2】

点击下载样例2 

【数据规模与约定】

对于 $50\%$ 的数据，$10 \lt n \leq 100，2 \leq m \leq 10$；

对于 $100\%$ 的数据，$10 \lt n \lt 3000，2 \leq m \leq 10，p_i \leq 2^{30}$；