Problem Description

Because your school’s schedule is so strange, your two classes will start at the same time in two different classrooms. You can only be in one place at a time, so you can only walk back and forth between the two rooms, hoping to catch the key parts of both classes.

The two classrooms are numbered $1$ and $2$. In classroom $i$, the teacher will show $N_{i}$ different slides. The $j$-th slide is shown during the time interval $\left(A_{i, j}, B_{i, j}\right)\left(0 \leq A_{i, j}<B_{i, j}\right)$, where $A_{i, j}$ and $B_{i, j}$ are times in seconds measured from the start of the class. In each classroom, there will never be multiple slides shown at the same time. For example, a class may show slides during $(1,2)$ and $(5,6)$, or during $(10,20)$ and $(20,30)$, but it will not show slides during $(10,20)$ and $(19,30)$.

You start the day in classroom $1$, and both classes start at time $0$. After that, at any moment (not necessarily an integer second), you may spend $K$ seconds moving from your current classroom to the other one. If you spend a positive amount of time in the correct classroom during a slide’s time interval, then you are considered to have seen that slide. During the $K$ seconds while you are moving between classrooms, you are in neither classroom, so you cannot see any slides.

For example, if classroom $1$ shows a slide during $(10,20)$, classroom $2$ shows a slide during $(15,25)$, and $K=8$, then if you move from classroom $1$ to classroom $2$ at time $11.5$ seconds (arriving at time $19.5$ seconds), you can see both slides. On the other hand, if you leave classroom $1$ at time $17$ seconds (arriving at time $25$ seconds), then you will enter classroom $2$ only after its slide stops 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 integers $N_{1}, N_{2}$, and $K$, separated by spaces.

The next $N_{1}$ lines each contain two integers $A_{1, i}$ and $B_{1, i}\left(1 \leq i \leq N_{1}\right)$, separated by spaces.

The next $N_{2}$ lines each contain two integers $A_{2, i}$ and $B_{2, i}\left(1 \leq i \leq N_{2}\right)$, separated by spaces.

Output Format

Output one integer, the maximum number of different slides you can see.

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

Hint

Explanation for Sample 1

One possible optimal strategy is to stay in classroom $1$ until time $11.5$, then move to classroom $2$ (arriving at time $19.5$), stay until time $19.6$, and finally return to classroom $1$ (arriving at time $27.6$). During this process, you will see all slides except the $3$-rd slide. It is impossible to see all $4$ slides.

Explanation for Sample 2

Even if you move to classroom $2$ immediately when the classes begin (for example, at time $0.0001$), you will miss the first two slides shown there. Therefore, you can see at most four slides.

Constraints

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

Translated by ChatGPT 5