Problem Description

When an airplane arrives at an airport, it can park at a jet bridge next to the terminal, or at a remote stand on the edge of the airport. Passengers usually prefer parking at a jet bridge, because it saves them the trouble of taking a shuttle bus to the terminal. However, since the number of jet bridges is limited, this wish cannot always be satisfied.

The airport is divided into a domestic area and an international area. Domestic flights can only park in the domestic area, and international flights can only park in the international area. Some jet bridges belong to the domestic area, and the remaining jet bridges belong to the international area.

City $L$ has built a new airport with a total of $n$ jet bridges. The airport decides that jet bridge usage follows the “first come, first served” rule: after each airplane arrives, if there is an available jet bridge in the corresponding area (domestic/international), it parks at a jet bridge; otherwise, it parks at a remote stand (assume the number of remote stands is sufficient). The airport has only one runway, so there will not be two airplanes arriving at the same time.

You are given the arrival and departure times of airplanes over a future period. Please allocate the $n$ jet bridges between the domestic area and the international area so that the number of airplanes that can park at jet bridges is maximized.

Input Format

The first line 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.

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.

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.

Integers on the same line are separated by spaces.

Output Format

Output one positive integer, the maximum possible number of airplanes that can park at jet bridges.

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

见附件中的 airport/airport3.in

见附件中的 airport/airport3.ans

Hint

[Sample Explanation #1]

In the figure, we use an ordered pair of arrival and departure times to represent a plane. For example, $(1, 5)$ means a plane arrives at time $1$ and departs at time $5$. We use $\surd$ to indicate that the plane parks at a jet bridge, and $\times$ to indicate that the plane parks at a remote stand.

We take the shaded part of the table as an example to explain the meaning of the table. In this part, the international area has $2$ jet bridges, and $4$ international planes arrive in the following order:

1. First, $(2, 11)$ arrives at time $2$ and parks at a jet bridge.
2. Then, $(4, 15)$ arrives at time $4$ and parks at the other jet bridge.
3. Next, $(7, 17)$ arrives at time $7$. At this time, the first $2$ planes have not departed and are still occupying the jet bridges. Since the international area has only $2$ jet bridges, it can only park at a remote stand.
4. Finally, $(12, 16)$ arrives at time $12$. At this time, the plane $(2, 11)$ has already departed, so there is $1$ available jet bridge, and this plane can park at a jet bridge.

According to the results in the table, when $2$ jet bridges are allocated to the domestic area and $1$ jet bridge is allocated to the international area, the number of planes that can park at jet bridges is maximized, with a total of $7$ planes.

[Sample Explanation #2]

When $2$ jet bridges are allocated to the domestic area and $0$ jet bridges are allocated to the international area, the number of planes that can park at jet bridges is maximized, with a total of $4$ planes, i.e. all domestic planes can park at jet bridges.

Note that in this problem, jet bridge usage follows the “first come, first served” rule. If the international area has only $1$ jet bridge, it will be occupied by the plane $(1, 19)$, and it will not be used in turn by the $4$ planes $(3, 4)$, $(5, 6)$, $(7, 8)$, $(9, 10)$.

[Constraints]

For $20\%$ of the testdata, $n \le 100$, $m_1 + m_2 \le 100$.
For $40\%$ of the testdata, $n \le 5000$, $m_1 + m_2 \le 5000$.
For $100\%$ of the testdata, $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 with values not exceeding ${10}^8$. 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}$.

[Thanks to the providers of hack data]

• xingxuxin。
• cyslngsul。

Translated by ChatGPT 5