Problem Description

Due to the overly abstract scheduling of your school, two of your classes will start simultaneously in two different classrooms! You can only be in one place at a time, so you plan to wander back and forth between the two classrooms, hoping to catch the highlights of both classes.

The classrooms are numbered $1$ and $2$. In classroom $i$, the teacher will present $N_i$ different slides, with the $j$-th slide being shown during the time interval $\left(A_{i, j}, B_{i, j}\right)$ where $0 \leq A_{i, j} < B_{i, j}$, and $A_{i, j}$ and $B_{i, j}$ are times in seconds measured from the start of the class. In both classrooms, no two slides are shown at the same time. For example, a class might have slides in the intervals $(1,2)$ and $(5,6)$, or in $(10,20)$ and $(20,30)$, but not in $(10,20)$ and $(19,30)$.

You start your day in classroom $1$, and both classes begin at time $0$. After that, you can move from your current classroom to the other one at any time (not necessarily an integer second) and it takes $K$ seconds. If you spend a positive amount of time in a classroom during the time interval of a slide's presentation, you consider yourself to have seen that slide. While you are moving between classrooms for $K$ seconds, you are not in either classroom, so you cannot see any slides during that time.

For example, if classroom $1$ shows a slide during the interval $(10,20)$ and classroom $2$ shows a slide during the interval $(15,25)$, and $K=8$, then if you move from classroom $1$ at $11.5$ seconds (arriving at $19.5$ seconds), you will see both slides. On the other hand, if you leave classroom $1$ at $17$ seconds (arriving at $25$ seconds), you will arrive after the slide in classroom $2$ has stopped being shown, so you will miss it.

You want to know the maximum number of different slides you can see.

Input Format

The first line contains three space-separated integers, $N_1$, $N_2$, and $K$.

The next $N_1$ lines each contain two space-separated integers $A_{1, i}$ and $B_{1, i}$ $(1 \leq i \leq N_1)$.

The next $N_2$ lines each contain two space-separated integers $A_{2, i}$ and $B_{2, i}$ $(1 \leq i \leq N_2)$.

Output Format

Output a single integer, representing the maximum number of different slides you can see.

Sample Input and Output

Sample Input #1

3 1 8
10 20
100 101
20 21
15 25

Sample Output #1

3

Sample Input #2

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

Sample Output #2

4

Notes/Hints

Sample 1 Explanation

One possible optimal strategy is to stay in classroom $1$ until $11.5$ seconds, then move to classroom $2$ (arriving at $19.5$ seconds), stay until $19.6$ seconds, and finally return to classroom $1$ (arriving at $27.6$ seconds). During this process, you will see all slides except the third one. It is not possible to see all four slides.

Sample 2 Explanation

Even if you immediately move to classroom $2$ at the start of the class (e.g., at $0.0001$ seconds), you will miss the first two slides shown there. Therefore, you can see at most four slides.

Data Range

For all data, $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$.

见题面 Input 部分

见题面 Output 部分