邮局加强版(Post Office)

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标表示。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

第一行包含两个整数：第一个是村庄的数量 $V$ ，第二个是邮局的数量 $P$ 。

第二行包含 $V$ 个整数。这些整数是村庄的位置。

第一行包含一个整数 $S$ ，它是每个村庄与其最近的邮局之间的所有距离的总和。

10 5 
1 2 3 6 7 9 11 22 44 50

对于 $40\%$ 的数据， $V \leq 300$ 。

对于 $100\%$ 的数据， $1 \leq P \leq 300$ ， $P \leq V \leq 3000$ ， $1 \leq$ 村庄位置 $\leq 10000$ 。

本题涉及的知识点从属于 NOI，难度（CF Rating）：2200。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~8	小规模 V≤50,P≤15 / 特殊: P=1单邮局取中位数 / 特殊: P=V每村一邮局距离0
2	15	9~11	Hack: 多村坐标完全重合 / Hack: 乱序输入村庄坐标 / Hack: 两端极端簇群分布
3	30	12~20	中规模 V≤500,P≤100 / 大规模 V=3000,P=300 四边形不等式压力
4	25	21~25	随机 P≤300,P≤V≤3000 回归

出处：原题链接

#P4767. 邮局加强版(Post Office)