Canadian Computing Olympiad: 2022 Day 1, Problem 3

Due to a rather ambitious school schedule, two of your classes are about to be held starting at exactly the same time, in two different classrooms! You can only be in one place at a time, so the best you can hope for is catching the important bits of both, even if that means sneaking back and forth between the two.

The two classrooms are numbered ~1~ and ~2~. In classroom ~i~, the teacher will show ~N_i~ different slides during the class, with the ~j^\text{th}~ slide shown throughout the exclusive time interval ~(A_{i,j}, B_{i,j})~ ~(0 \le A_{i,j} < B_{i,j})~ where ~A_{i,j}~ and ~B_{i,j}~ are times elapsed since the start of class measured in seconds. In both classes, there does not exist a point in time at which multiple slides are simultaneously being shown. For example, a class may have slides spanning the pair of intervals ~(1, 2)~ and ~(5, 6)~, or the pair ~(10, 20)~ and ~(20, 30)~, but not the pair ~(10, 20)~ and ~(19, 30)~.

You begin the day in classroom ~1~ with both classes starting at time ~0~. Following that, at any point in time (not necessarily after an integral number of seconds), you may move from your current classroom to the other one in ~K~ seconds. You consider yourself to have seen a slide if you spend a positive amount of time in its classroom strictly within the time interval during which it's being shown. When moving between the two classrooms, you're not considered to be inside either of them for ~K~ seconds and are thus unable to see any slides.

For example, if classroom ~1~ has a slide being shown for the time interval ~(10, 20)~, classroom ~2~ has a slide being shown for the time interval ~(15, 25)~, and ~K = 8~, then you'll get to see both slides if you move from classroom ~1~ to classroom ~2~ at time ~11.5~ seconds (arriving at time ~19.5~ seconds). On the other hand, if you leave classroom ~1~ at time ~17~ seconds (arriving at time ~25~ seconds), then you'll enter classroom ~2~ just after its slide stops being shown and will therefore miss it.

What's the maximum number of distinct slides which you can see at least once?

Input Specification

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 \le i \le N_1)~.

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

Marks Awarded	Bounds on ~N_i~	Bounds on ~A_{i,j}~ and ~B_{i,j}~	Bounds on ~K~
~5~ marks	~1 \le N_i \le 10~	~0 \le A_{i,j} < B_{i,j} \le 2\,000~	~1 \le K \le 10^9~
~10~ marks	~1 \le N_i \le 2\,000~	~0 \le A_{i,j} < B_{i,j} \le 2\,000~	~1 \le K \le 10^9~
~6~ marks	~1 \le N_i \le 2\,000~	~0 \le A_{i,j} < B_{i,j} \le 10^9~, ~B_{i,j}-A_{i,j} \le 2K~	~1 \le K \le 10^9~
~4~ marks	~1 \le N_i \le 300\,000~	~0 \le A_{i,j} < B_{i,j} \le 10^9~	~1 \le K \le 10^9~

Output Specification

Output one integer which is the maximum number of distinct slides which you can see.

Sample Input 1

3 1 8
10 20
100 101
20 21
15 25

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

One possible optimal strategy is to remain in classroom ~1~ until time ~11.5~, then move to classroom ~2~ (arriving at time ~19.5~), remain there until time ~19.6~, and finally return to classroom ~1~ (arriving at time ~27.6~). In the process, you'll see all but the ~3^\text{rd}~ slide. It's impossible for you to see all 4 slides.

Sample Input 2

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

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

Even if you begin moving to classroom ~2~ immediately at the start of the classes (e.g., at time ~0.0001~), you'll miss the first ~2~ slides shown there. As such, it is possible to see a total of at most four slides.