{"problem":{"name":"[CCO 2022] Double Attendance","description":{"content":"由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。 两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\\left(A_{i, j}, B_{i, j}\\right)\\left(0 \\leq A_{i,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10052"},"statements":[{"statement_type":"Markdown","content":"由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。\n\n两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\\left(A_{i, j}, B_{i, j}\\right)\\left(0 \\leq A_{i, j}<B_{i, j}\\right)$ 内展示，其中 $A_{i, j}$ 和 $B_{i, j}$ 是从课堂开始后以秒为单位计算的时间。在两个教室里，不会在某个时间点同时展示多张幻灯片。例如，一个课堂可能在 $(1,2)$ 和 $(5,6)$ 这两对时间区间内有幻灯片展示，或者在 $(10,20)$ 和 $(20,30)$ 这两对时间区间内有幻灯片展示，但不会在 $(10,20)$ 和 $(19,30)$ 这两对时间区间有幻灯片展示。\n\n你在教室 $1$ 开始一天的课程，两门课程都在时刻 $0$ 开始。在那之后，你可以在任何时间点（不一定是整数秒）花费 $K$ 秒从你当前的教室移动到另一个教室。如果你在展示幻灯片的时间区间内在其教室里花费了正数时间，你就认为自己看到了这张幻灯片。当你在两个教室之间移动的 $K$ 秒内，你不在任何一个教室里，因此无法看到任何幻灯片。\n\n例如，如果教室 $1$ 在时间区间 $(10,20)$ 展示一张幻灯片，教室 $2$ 在时间区间 $(15,25)$ 展示一张幻灯片，而 $K=8$，那么如果你在时间 $11.5$ 秒时从教室 $1$ 移动到教室 $2$（到达时间为 $19.5$ 秒），你就能看到两张幻灯片。另一方面，如果你在时间 $17$ 秒时离开教室 $1$（到达时间为 $25$ 秒），那么你将在教室 $2$ 的幻灯片停止展示后才进入教室，因此你会错过它。\n\n你想要知道你能看到的不同幻灯片的最大数量是多少。\n\n## Input\n\n第一行包含三个用空格分隔的整数，$N_{1}, N_{2}$ 和 $K$。\n\n接下来的 $N_{1}$ 行，每行包含两个用空格分隔的整数 $A_{1, i}$ 和 $B_{1, i}\\left(1 \\leq i \\leq N_{1}\\right)$。\n\n接下来的 $N_{2}$ 行，每行包含两个用空格分隔的整数，$A_{2, i}$ 和 $B_{2, i}\\left(1 \\leq i \\leq N_{2}\\right)$。\n\n## Output\n\n输出一个整数，表示你能看到的不同幻灯片的最大数量。\n\n[samples]\n\n## Note\n\n## 样例 1 解释\n\n一种可能的最优策略是在教室 $1$ 一直待到时间 $11.5$，然后移动到教室 $2$（到达时间为 $19.5$），一直待到时间 $19.6$，最后返回教室 $1$（到达时间为 $27.6$）。在这个过程中，你将看到除了第 $3$ 张幻灯片以外的所有幻灯片。你不可能看到所有的 $4$ 张幻灯片。\n\n## 样例 2 解释\n\n即使你在课程开始时立即移动到教室 $2$（例如，在时间 $0.0001$），你也会错过那里展示的前两张幻灯片。因此，你最多可以看到四张幻灯片。\n\n## 数据范围\n对于所有的数据，有 $1 \\leq N_{i} \\leq 3\\times 10^5$，$0 \\leq A_{i, j}<B_{i, j} \\leq 10^{9}$，$1 \\leq K \\leq 10^{9}$。\n\n子任务编号|分值|$N_{i}$|$A_{i, j},B_{i, j}$\n:-:|:-:|:-:|:-:\n$1$|$20$|$1 \\leq N_{i} \\leq 10$|$0 \\leq A_{i, j}<B_{i, j} \\leq 2000$\n$2$|$40$|$1 \\leq N_{i} \\leq 2000$|$0 \\leq A_{i, j}<B_{i, j} \\leq 2000$\n$3$|$24$|$1 \\leq N_{i} \\leq 2000$|$B_{i, j}-A_{i, j} \\leq 2 K$\n$4$|$16$|$1 \\leq N_{i} \\leq 3\\times 10^5$|$0 \\leq A_{i, j}<B_{i, j} \\leq 10^{9}$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10052","tags":["2022","CCO（加拿大）"],"sample_group":[["3 1 8\n10 20\n100 101\n20 21\n15 25","3"],["1 5 3\n1 100\n1 2\n2 3\n3 4\n4 5\n5 6","4"]],"created_at":"2026-03-03 11:09:25"}}