A89661.「USACO 2025 US Open Platinum」Package Pickup

题目译自 USACO 2025 US Open Contest, Platinum Problem 3. Package Pickup

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

Farmer John 用一种奇特的方式在数轴上分布了牛群和包裹，过程如下：

• Farmer John 选定一个数字 $M$（$1 \le M \le 10^{18}$）。
• 他挑出 $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, \dots, R_i$ 的位置上。保证 $R_i - L_i$ 是 $M$ 的倍数。
• 他还选出 $P$（$1 \le P \le 2 \cdot 10^4$）个区间 $[A_j, B_j]$（$1 \le A_j \le B_j \le 10^{18}$）来放置包裹。包裹会被安置在 $A_j, A_j + M, A_j + 2M, \dots, B_j$ 的位置上。保证 $B_j - A_j$ 是 $M$ 的倍数。

牛群和包裹分布好后，Farmer John 想知道牛群需要多少时间才能捡完所有包裹。每秒钟，他可以用对讲机指挥一头牛向左或向右移动一个单位。如果某头牛到达包裹所在的位置，就能捡起它。Farmer John 希望你帮他算出最短需要多少秒，让所有包裹都被捡起来。

第一行包含三个整数 $M$、$N$ 和 $P$。

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

再接下来的 $P$ 行，每行包含两个整数 $A_j$ 和 $B_j$。

输出一个整数，表示牛群捡起所有包裹所需的最短时间（单位：秒）。每秒钟只能对一头牛发出一次左移或右移的指令。