第 2 题巨大的城市 (`largecity`)

时间限制 1.0 s · 空间限制 256 MB · 89 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 largecity.in，输出文件 largecity.out。

题目描述

KOI 市太大了，移动时需要花费很长时间。为了解决这个问题，KOI 市修建了一条贯穿全城的超长道路。这些道路朝南北方向或东西方向无限延伸。南北方向的道路共有 $N$ 条，东西方向的道路共有 $M$ 条。道路的宽度可以忽略不计。

若以 KOI 市市政府为原点在坐标平面上绘制城市，则南北方向的道路可表示为 $x = a_i$ （ $1 \le i \le N$ ）的直线，东西方向的道路可表示为 $y = b_j$ （ $1 \le j \le M$ ）的直线。例如，下图展示了 $x = 3$ 的道路和 $y = 2$ 的道路。请注意，尽管图中道路是有限长度，但实际这些道路是无限延伸的。

在这 $N + M$ 条道路中，有 $K$ 条道路上各派驻了一名警察以防止超速。第 $k$ （ $1 \le k \le K$ ）名警察的位置是 $(p_k, q_k)$ ，且每名警察必定位于其负责的道路上。

例如，图中有一名警察被派驻在 $x = 3$ 的道路上 $(3, -2)$ 处，另一名警察被派驻在 $y = 2$ 的道路上 $(-4, 2)$ 处。某些道路上可能没有警察，但如果某条道路上有警察，则只会有一名。

警察只能沿道路移动。如果两条道路交叉，则警察可以在交点处切换到另一条道路，切换过程无需耗费距离。

如下图所示，一名警察可以从 $x = 3$ 的道路上 $(3, -2)$ 处出发，经由交点 $(3, 2)$ 切换到 $y = 2$ 的道路上，从而移动到另一名警察所在的位置，所需移动总距离为 11。

警察需要在紧急情况下能够迅速会合。因此，你的任务是：对于所有可能的两两警察组合，计算他们最短的相遇距离，并输出所有这些最短距离的总和。

在这个例子中，共有 3 种可能的组合：

位于 $y = 2$ 道路的警察与位于 $x = -4$ 道路的警察会合。这种情况下，两位警察至少需要移动 3 单位距离才能相遇。
位于 $y = 2$ 道路的警察与位于 $x = 3$ 道路的警察会合。这种情况下，两位警察至少需要移动 11 单位距离才能相遇。
位于 $x = -4$ 道路的警察与位于 $x = 3$ 道路的警察会合。这种情况下，两位警察至少需要移动 12 单位距离才能相遇。

因此，总和为 26。虽然有两名警察的 $x$ 坐标都是 $-4$ ，但警察 $(-4, 2)$ 是驻扎在 $y = 2$ 道路上的，而警察 $(-4, -1)$ 则在 $x = -4$ 道路上，所以这样的输入是有效的，请注意此类情况。

请你编写一个程序，给定 KOI 市的道路和警察的位置，计算如上所述的所有警察两两之间最短相遇距离的总和。

输入格式

第一行输入三个整数 $N, M, K$ ，以空格分隔。

第二行输入 $N$ 个整数 $a_1, a_2, \dots, a_N$ ，以空格分隔，表示南北方向道路的 $x$ 坐标。

第三行输入 $M$ 个整数 $b_1, b_2, \dots, b_M$ ，以空格分隔，表示东西方向道路的 $y$ 坐标。

接下来 $K$ 行，每行两个整数 $p_k, q_k$ ，表示第 $k$ 名警察的位置。

输出格式

输出一个整数，表示所有两两警察组合的最短相遇距离之和。

样例

样例 1

输入：

输出：

样例 2

输入：

输出：

提示

约束条件

所有输入均为整数。
$1 \le N \le 100\,000$
$1 \le M \le 100\,000$
$2 \le K \le N + M$
$-100\,000 \le a_i \le 100\,000$ （ $1 \le i \le N$ ）
$-100\,000 \le b_j \le 100\,000$ （ $1 \le j \le M$ ）
$-100\,000 \le p_k, q_k \le 100\,000$ （ $1 \le k \le K$ ）
所有 $a_i$ 互不相同，所有 $b_j$ 互不相同，所有警察位置 $(p_k, q_k)$ 互不相同
每条道路上最多只有一名警察

子任务

（14 分） $M = 1$
（11 分）所有警察都仅驻扎在两条道路的交点上
（20 分） $1 \le N, M \le 20$
（25 分） $1 \le N, M \le 1000$
（30 分）无附加限制

第 2 题 巨大的城市 (largecity)