Description

注意：本题的时间限制为 4 秒，是默认值的 2 倍。

农夫约翰（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$ 的倍数。

一旦奶牛和包裹分布完毕，农夫约翰想知道奶牛们捡起所有包裹需要多长时间。每一秒，农夫约翰可以用他方便的对讲机（walkie talkie）向一头奶牛发出指令，让其从当前位置向左或向右移动一个单位。如果一头奶牛移动到包裹所在的位置，它就能捡起该包裹。农夫约翰想知道，奶牛们捡起所有包裹所需的最少时间（以秒为单位）。

Input Format

第一行包含 $M$、$N$ 和 $P$。

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

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

Output Format

输出一个整数，表示奶牛们捡起所有包裹所需的最少时间，前提是每一秒他只能向一头奶牛发出一次向左/向右的指令。

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

Hint

样例 1 解释

在上面的测试用例中，假设奶牛和包裹从左到右编号。农夫约翰可以按照以下步骤在 22 秒内捡起所有包裹：

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

测试点限制

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