#P2769. 猴子上树

猴子上树

题目描述

在猴村有一条笔直的山路,这条山路很窄,宽度忽略不计。有 nn 只猴子正站在山路上静静地观望偷偷打游戏的Dream_not_found。用一个正整数 XiX_i 表示第 ii 只猴子所站位置,任意两只猴子的所站位置互不相同。在这条山路的 mm 个位置上种着一些高大的树木,正整数 YjY_j 表示第 jj 棵树木所在的位置,任意两棵树的位置互不相同。

正当猴子们聚精会神地欣赏Dream_not_found高超的游戏技巧时,一只老虎大摇大摆地走了过来。猴子们吓得直冒冷汗,第一反应就是找棵大树爬上去,这样能避免被老虎咬死或者吃掉(不考虑老虎上树问题)。

在位置 aa 的猴子跑到在位置 bb 的大树上,需要消耗能量为 ab|a-b|(即 aba-b 的绝对值)。为了尽可能有效利用这些大树避难,每棵上至少要一只猴子。 请编程计算 nn 只猴子全部上树最少需要消耗多少能量?

输入格式

输入共 4 行。

第 1 行一个整数 nn,表示猴子的数量。

第 2 行 nn 个整数,第 ii 个整数 XiX_i 表示第 ii 只猴子所在的位置。

第 3 行一个整数 mm,表示大树的数量。

第 4 行 mm 个整数,第 jj 个整数表示第 jj 棵大树所在的位置。

输出格式

输出一行,一个整数表示 nn 只猴子全部上树最少需要消耗的能量。

3
1 4 5
2
3 8
6
3
3 1 10
2
8 3
4

提示

3030% 的数据,1n5001\le n \le 5001Xi,Yi1051≤X_i,Y_i≤10^5

100100% 的数据,1n50001≤n≤50001mn1≤m≤n1Xi,Yi1091≤Xi,Yi≤10^9