P12689 [KOI 2022 Round 1] 巨大的城市

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 市太大了，移动时需要花费很长时间。为了解决这个问题，KOI 市修建了一条贯穿全城的超长道路。这些道路朝南北方向或东西方向无限延伸。南北方向的道路共有 $N$ 条，东西方向的道路共有 $M$ 条。道路的宽度可以忽略不计。 若以 KOI 市市政府为原点在坐标平面上绘制城市，则南北方向的道路可表示为 $x = a_i\ (1 \leq i \leq N)$ 的直线，东西方向的道路可表示为 $y = b_j\ (1 \leq j \leq M)$ 的直线。例如，下图展示了 $x = 3$ 的道路和 $y = 2$ 的道路。请注意，尽管图中道路是有限长度，但实际这些道路是无限延伸的。  在这 $N + M$ 条道路中，有 $K$ 条道路上各派驻了一名警察以防止超速。第 $k\ (1 \leq k \leq 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, \cdots, a_N$，以空格分隔，表示南北方向道路的 $x$ 坐标。 第三行输入 $M$ 个整数 $b_1, b_2, \cdots, b_M$，以空格分隔，表示东西方向道路的 $y$ 坐标。 接下来 $K$ 行，每行两个整数 $p_k$, $q_k$，表示第 $k$ 名警察的位置。

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

**约束条件** - 所有输入均为整数。 - $1 \leq N \leq 100\,000$ - $1 \leq M \leq 100\,000$ - $2 \leq K \leq N + M$ - $-100\,000 \leq a_i \leq 100\,000\quad (1 \leq i \leq N)$ - $-100\,000 \leq b_j \leq 100\,000\quad (1 \leq j \leq M)$ - $-100\,000 \leq p_k, q_k \leq 100\,000\quad (1 \leq k \leq K)$ - 所有 $a_i$ 互不相同，所有 $b_j$ 互不相同，所有警察位置 $(p_k, q_k)$ 互不相同 - 每条道路上最多只有一名警察 **子任务** 1. （14 分）$M = 1$ 2. （11 分）所有警察都仅驻扎在两条道路的交点上 3. （20 分）$1 \leq N, M \leq 20$ 4. （25 分）$1 \leq N, M \leq 1\,000$ 5. （30 分）无附加限制