题目描述

由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。

两个教室的编号分别是 $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)$ 这两对时间区间有幻灯片展示。

你在教室 $1$ 开始一天的课程，两门课程都在时刻 $0$ 开始。在那之后，你可以在任何时间点（不一定是整数秒）花费 $K$ 秒从你当前的教室移动到另一个教室。如果你在展示幻灯片的时间区间内在其教室里花费了正数时间，你就认为自己看到了这张幻灯片。当你在两个教室之间移动的 $K$ 秒内，你不在任何一个教室里，因此无法看到任何幻灯片。

例如，如果教室 $1$ 在时间区间 $(10,20)$ 展示一张幻灯片，教室 $2$ 在时间区间 $(15,25)$ 展示一张幻灯片，而 $K=8$，那么如果你在时间 $11.5$ 秒时从教室 $1$ 移动到教室 $2$（到达时间为 $19.5$ 秒），你就能看到两张幻灯片。另一方面，如果你在时间 $17$ 秒时离开教室 $1$（到达时间为 $25$ 秒），那么你将在教室 $2$ 的幻灯片停止展示后才进入教室，因此你会错过它。

你想要知道你能看到的不同幻灯片的最大数量是多少。

输入格式

第一行包含三个用空格分隔的整数，$N_{1}, N_{2}$ 和 $K$。

接下来的 $N_{1}$ 行，每行包含两个用空格分隔的整数 $A_{1, i}$ 和 $B_{1, i}\left(1 \leq i \leq N_{1}\right)$。

接下来的 $N_{2}$ 行，每行包含两个用空格分隔的整数，$A_{2, i}$ 和 $B_{2, i}\left(1 \leq i \leq N_{2}\right)$。

输出格式

输出一个整数，表示你能看到的不同幻灯片的最大数量。

3 1 8
10 20
100 101
20 21
15 25

3

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

4

提示

样例 1 解释

一种可能的最优策略是在教室 $1$ 一直待到时间 $11.5$，然后移动到教室 $2$（到达时间为 $19.5$），一直待到时间 $19.6$，最后返回教室 $1$（到达时间为 $27.6$）。在这个过程中，你将看到除了第 $3$ 张幻灯片以外的所有幻灯片。你不可能看到所有的 $4$ 张幻灯片。

样例 2 解释

即使你在课程开始时立即移动到教室 $2$（例如，在时间 $0.0001$），你也会错过那里展示的前两张幻灯片。因此，你最多可以看到四张幻灯片。

数据范围

对于所有的数据，有 $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}$。