In one large city, they are preparing to open a new branch of the surface metro. It runs between two cities in the suburbs on opposite sides of the city itself, but passing through it throughout. This model of surface metro was called the City Central Diameters (CDC).
In preparation for the launch of the GDC, a special schedule was developed, containing n flights in one direction and m flights in the opposite direction. For each flight, a
i - time of departure from the first end station and b
i - time of arrival at the second end station, for return flights c
j is the time of departure from the second station and dj is the time of arrival at the first station. Times are measured in minutes from the start of the day. Inside a big city, trains can
travel on different routes, so a train that left later than some other train may arrive before it.
Projects of this magnitude have not yet been launched, which means that unforeseen events will occur and trains will be delayed. Analysts of the company serving the GDC calculated that under any circumstances, the train can be late for the final station by no more than t minutes. The train can start the next run as soon as it has finished the previous one.
The company was instructed to ensure the implementation of each flight at all costs. Determine what is the minimum number of trains you need to have so that no flight is guaranteed to be canceled even in case of possible delays of all trains. Trains must depart from
starting stations strictly according to the schedule.
At the beginning and at the end of the day, trains can be at any of the stations. Trains cannot move between stations during the day, except according to this schedule.
Input data format
The first line of the input contains the maximum flight delay t, 0 <= t <= 109.
The next line contains the number n - the number of flights in the schedule one way, 0 <= n <= 100. The next 2n lines contain the numbers a1, b1 , a2, b2, ..., an, bn - departure time trains from the first station and the time of their arrival at the second station, 0 <= ai < bi <= 109.
The next line contains the number m - the number of trains in the timetable in the opposite direction, 0 <= m <= 100. The next 2m lines contain the departure time cj and the arrival time dj trains in the opposite direction in the same format, 0 <= cj < dj <= 109.
The trains in the timetable are listed in random order, not necessarily in ascending order of time.
Output data format
The program should print a single integer - the minimum number of trains needed to complete the given schedule.
| Input |
Output |
4
2
3
8
5
10
1
11
15 |
3 |
1
2
15
18
7
9
2
11
14
1
3 |
1 |