#3791. [Poi1999]地图

[Poi1999]地图

[POI1999]地图

题目背景

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

题目描述

由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色 kk,则 A(k)A(k) 是相应的数,则有:

  • 在用颜色kk的区域中至少有一半的区域的人口不大于 A(k)A(k)
  • 在用颜色kk的区域中至少有一半的区域的人口不小于 A(k)A(k)

区域颜色误差是该区域的人口与 A(k)A(k) 差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案,使得累计误差最小。

输入格式

第一行有一个整数 nn,表示区域数。

在第二行中的数 mm 表示颜色数。

在接下来的 nn 行中每行有一个非负整数,表示一个区域的人口。

人口都不超过 2302^{30}

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

15

提示

对于 100%100\% 的数据,10<n<300010< n <30002m102 \le m \le 10