[AdditionalFile4884.zip](file://AdditionalFile4884.zip?type=additional_file)

#4884. 「USACO 2025 US Open Platinum」Package Pickup

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 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 可以通过他便利的对讲机向一头奶牛发出命令，令其从当前位置向左或向右移动一个单位。如果一头奶牛移动到包裹所在的位置，她们就能够捡起包裹。Farmer John 想要知道奶牛们捡起所有包裹所需要的最少秒数。

输入格式

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

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

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

输出格式

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

样例 1

输入

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

输入

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