Problem 3. Package Pickup

USACO 2025 US Open Contest, Platinum

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

Farmer John 在数轴上通过以下过程以一种奇怪的模式放置了奶牛和包裹：

• Farmer John 选择一个数字 $M$（$1 \le M \le 10^{18}$）。
• Farmer John 选择 $N$（$1 \le N \le 2 \cdot 10^4$）个区间 $[L_i, R_i]$ 以在其中放置奶牛（$1 \le L_i \le R_i \le 10^{18}$）。他随后在位置 $L_i, L_i + M, L_i + 2M, \ldots, R_i$ 放置奶牛。输入保证 $R_i - L_i$ 是 $M$ 的倍数。
• Farmer John 选择 $P$（$1 \le P \le 2 \cdot 10^4$）个区间 $[A_i, B_i]$ 以在其中放置包裹（$1 \le A_i \le B_i \le 10^{18}$）。他随后在位置 $A_i, A_i + M, A_i + 2M, \ldots, B_i$ 放置包裹。输入保证 $B_i - A_i$ 是 $M$ 的倍数。

当奶牛和包裹被放置后，Farmer John 想要知道奶牛们捡起包裹需要多长时间。每一秒，Farmer John 可以通过他便利的对讲机向一头奶牛发出命令，令其从当前位置向左或向右移动一个单位。如果一头奶牛移动到包裹所在的位置，她们就能够捡起包裹。Farmer John 想要知道奶牛们捡起所有包裹所需要的最少秒数。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $M$，$N$ 和 $P$。

以下 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$。

以下 $P$ 行，每行包含两个整数 $A_i$ 和 $B_i$。

输出格式（输出至终端 / 标准输出）：

输出一个整数，表示当每一秒他可以向一头奶牛发出一个左/右命令时，奶牛们捡起所有包裹所需要的最短时间。

输入样例：

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

输出样例：

22

在以上测试用例中，假设奶牛和包裹从左到右编号。Farmer John 可以按以下过程在 22 秒内捡起包裹：

• 向奶牛 $1$ 发出 $3$ 次向左命令使其捡起包裹 $1$
• 向奶牛 $3$ 发出 $3$ 次向右命令使其捡起包裹 $7$
• 向奶牛 $2$ 发出 $4$ 次向右命令使其捡起包裹 $5$
• 向奶牛 $1$ 发出 $10$ 次向右命令使其捡起包裹 $2$，$3$ 和 $4$
• 向奶牛 $2$ 发出 $2$ 次向右命令使其捡起包裹 $6$

输入样例：

2 1 1
1 5
2 6

输出样例：

3

有三头奶牛和三个包裹。Farmer John 可以向每一头奶牛发出一次向右命令。

测试点性质： 测试点 3-4：输入保证奶牛与包裹的数量之和不超过 $2 \cdot 10^5$。测试点 5-10：输入保证 $N, P \le 500$。测试点 11-13：输入保证奶牛与包裹的区间两两不相交。测试点 14-20：没有额外限制。

供题：Suhas Nagar，Benjamin Qi