06779. USACO·包裹收集 未做

注意：本题的时间限制为 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,\dots ,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,\dots ,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$。

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

【样例解释】

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

• 测试点 5-10：输入保证 $N,P\le 500$。

• 测试点 11-13：输入保证奶牛与包裹的区间两两不相交。

• 测试点 14-20：没有额外限制。

【数据规模与约定】

• 测试点 3-4：输入保证奶牛与包裹的数量之和不超过 $2\cdot 10^5$。

• 测试点 5-10：输入保证 $N,P\le 500$。

• 测试点 11-13：输入保证奶牛与包裹的区间两两不相交。

• 测试点 14-20：没有额外限制。

供题：Suhas Nagar，Benjamin Qi