P2769 猴子上树

题目描述

在猴村有一条笔直的山路,这条山路很窄,宽度忽略不计。有 $n$ 只猴子正站在山路上静静地观望今天来参加比赛的各位同学。用一个正整数 $X_i$ 表示第 $i$ 只猴子所站位置,任意两只猴子的所站位置互不相同。在这条山路的 $m$ 个位置上种着一些高大的树木,正整数 $Y_j$ 表示第 $j$ 棵树木所在的位置,任意两棵树的位置互不相同。 正当猴子们聚精会神的欣赏各位高超编程技能 聚精会神的欣赏各位高超编程技能时,一只老虎大摇摆的走了过来。猴子们吓得直冒冷汗,第一反应就是找棵大树爬上去这样能避免被老虎咬死或者吃掉(不考虑老虎上树问题)。 在位置 $a$ 的猴子跑到在位置 $b$ 的大树上,需要消耗能量为 $|a-b|$(即 $a-b$ 的绝对值)。为了尽可能有效利用这些大树避难,每棵上至少要一只猴子。 请编程计算 $n$ 只猴子全部上树最少需要消耗多少能量?

输入格式

输出格式

说明/提示

$30%$ 的数据,$1\le n \le 500$,$1≤X_i,Y_i≤10^5$。 $100%$ 的数据,$1≤n≤5000$,$1≤m≤n$,$1≤Xi,Yi≤10^9$。