题目描述

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

输出格式

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

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

22

2 1 1
1 5
2 6

3

测试点性质

• 测试点 3-4：保证奶牛和包裹的总数不超过 $2 \cdot 10^5$。
• 测试点 5-10：保证 $N, P \le 500$。
• 测试点 11-13：保证包裹或奶牛的区间均不相交。
• 测试点 14-20：没有额外限制。

供题：Suhas Nagar 和 Benjamin Qi