Person in Charge

• SleepingCup

Problem Description

When an airplane arrives at an airport, it can either dock at a jet bridge next to the terminal building or at a remote stand located on the edge of the airport. Passengers generally prefer docking at a jet bridge, as this eliminates the hassle of taking a shuttle bus to the terminal building. However, due to the limited number of jet bridges, this wish cannot always be fulfilled.

The airport is divided into a domestic zone and an international zone. Domestic flights can only dock in the domestic zone, while international flights can only dock in the international zone. Some of the jet bridges belong to the domestic zone, and the rest belong to the international zone.

A new airport has been built in City L, with a total of $n$ jet bridges. The airport has decided that the use of jet bridges follows the "first-come, first-served" principle: when an airplane arrives, if there is an available jet bridge in the corresponding zone (domestic/international), it will dock at the jet bridge; otherwise, it will dock at a remote stand (assuming there are sufficient remote stands). The airport has only one runway, so no two airplanes arrive at the same time.

Given the arrival and departure times of airplanes for a future period, your task is to allocate the $n$ jet bridges between the domestic and international zones to maximize the number of airplanes that can dock at jet bridges.

Input Format

The first line of input contains three positive integers $n, m_1, m_2$, representing the number of jet bridges, the number of domestic flights, and the number of international flights, respectively.

The next $m_1$ lines contain information about domestic flights. The $i$-th line contains two positive integers $a_{1, i}, b_{1, i}$, representing the arrival and departure times of a domestic flight airplane.

The next $m_2$ lines contain information about international flights. The $i$-th line contains two positive integers $a_{2, i}, b_{2, i}$, representing the arrival and departure times of an international flight airplane.

Multiple integers in each line are separated by spaces.

Output Format

Output a positive integer, representing the maximum number of airplanes that can dock at jet bridges.

Samples

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

7

2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10

4

Sample 1 Explanation

In the figure, we use pairs of arrival and departure times to represent an airplane (e.g., $(1, 5)$ denotes an airplane that arrives at time $1$ and departs at time $5$); $\surd$ indicates that the airplane docks at a jet bridge, and $\times$ indicates that it docks at a remote stand.

Taking the calculation method of the shaded part in the table as an example, we explain the meaning of the table. In this part, the international zone has $2$ jet bridges, and the $4$ international flights arrive in the following order:

1. First, $(2, 11)$ arrives at time $2$ and docks at a jet bridge.
2. Then, $(4, 15)$ arrives at time $4$ and docks at another jet bridge.
3. Next, $(7, 17)$ arrives at time $7$. At this time, the first two airplanes have not yet departed and are still occupying the jet bridges, and the international zone only has $2$ jet bridges, so it has to dock at a remote stand.
4. Finally, $(12, 16)$ arrives at time $12$. At this time, the airplane $(2, 11)$ has departed, so there is $1$ available jet bridge, and this airplane can dock at the jet bridge.

According to the calculation results in the table, when $2$ jet bridges are allocated to the domestic zone and $1$ to the international zone, the number of airplanes docking at jet bridges is maximized, with a total of $7$ airplanes.

Sample 2 Explanation

When $2$ jet bridges are allocated to the domestic zone and $0$ to the international zone, the number of airplanes docking at jet bridges is maximized, with a total of $4$ airplanes (i.e., all domestic flights can dock at jet bridges).

It should be noted that the use of jet bridges in this problem follows the "first-come, first-served" principle. If the international zone has only $1$ jet bridge, it will be occupied by the airplane $(1, 19)$ and will not be used by the four airplanes $(3, 4)$, $(5, 6)$, $(7, 8)$, and $(9, 10)$ in sequence.

Sample 3

See airport/airport3.in and airport/airport3.ans in the contestant's directory.

Data Range

• For $20\%$ of the data: $n \le 100$, $m_1 + m_2 \le 100$.
• For $40\%$ of the data: $n \le 5000$, $m_1 + m_2 \le 5000$.
• For $100\%$ of the data: $1 \le n \le 10^5$, $m_1, m_2 \ge 1$, $m_1 + m_2 \le 10^5$. All $a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}$ are distinct positive integers not exceeding $10^8$, and it is guaranteed that for each $i \in [1, m_1]$, $a_{1, i} < b_{1, i}$, and for each $i \in [1, m_2]$, $a_{2, i} < b_{2, i}$.