Maximizing Slide Coverage in Dual-Class Scheduling

You are enrolled in two courses that start at the same time in two different classrooms: room 1 and room 2. In classroom i, the teacher presents N_i distinct slides. The j-th slide in room i is shown during the time interval \( (A_{i,j}, B_{i,j}) \) seconds (with \(0 \le A_{i,j} < B_{i,j}\)). In each classroom, no two slides overlap: slides may be shown in intervals such as \( (1,2) \) and \( (5,6) \) or even consecutively like \( (10,20) \) and \( (20,30) \), but intervals such as \( (10,20) \) and \( (19,30) \) will never occur.

You start the day in classroom 1 at time \(0\), and both classes begin at this time. Since you can only be in one classroom at a time, you might decide to switch between them. Switching from one classroom to the other takes exactly \(K\) seconds during which you are not in any classroom and therefore miss all slides.

You are considered to have seen a slide if you spend a positive amount of time in its classroom during its display interval. Your task is to determine the maximum number of distinct slides you can see by strategically choosing when to switch classrooms.

Input Note: All time values are measured in seconds, and the time intervals for slides in each classroom are given in increasing order (and do not overlap within the same classroom).

inputFormat

The input begins with three numbers: K (the time in seconds it takes to switch classrooms), N1 (the number of slides in classroom 1), and N2 (the number of slides in classroom 2).

This is followed by N1 lines, each containing two numbers A1,j and B1,j indicating the start and end times of the slide in classroom 1. Then, there are N2 lines, each with two numbers A2,j and B2,j for the slides in classroom 2.

It is guaranteed that within each classroom the slide intervals are non-overlapping and sorted by start time.

outputFormat

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

sample

8 1 1
10 20
15 25

2