题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

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$ 名警察的位置。

输出格式

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

2 2 3
-4 3
2 -4
-4 2
-4 -1
3 -2

26

2 3 5
-2 5
5 -3 2
-1 5
0 2
4 -3
5 4
-2 -2

88

提示

约束条件

• 所有输入均为整数。
• $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 分）无附加限制