Optimizing Jet Bridge Allocation

An airport has n jet bridges that can be allocated to either the domestic or international terminal. Domestic flights can only dock at bridges in the domestic zone while international flights can only dock at bridges in the international zone. When a plane arrives, it will use a jet bridge if one is available in the appropriate zone, otherwise it will use a remote stand (assume there are enough remote stands).

The airport operates under a first-come, first-served rule. When a plane arrives, if there is a free jet bridge in its respective zone, it occupies that bridge until it departs. Otherwise, the plane is assigned to a remote stand. Prior to any arrivals, you must determine how to split the n jet bridges between the two zones in order to maximize the total number of flights that can be served by a jet bridge.

Formally, you are given a total of n jet bridges and the schedules of m₁ domestic flights and m₂ international flights. For each flight, you are provided with its arrival time and departure time. If you allocate x jet bridges to the domestic zone and n-x to the international zone, let F_domestic(x) be the number of domestic flights that can be accommodated and F_{international}(n-x) be the number of international flights that can be accommodated. Your task is to choose x (where 0 \le x \le n) so that the sum

[ F_{domestic}(x) + F_{international}(n-x) ]

is maximized. Note that all time values are positive integers and no two flights arrive at the same time.

inputFormat

The first line contains three integers: n (1 \le n), m₁ (number of domestic flights), and m₂ (number of international flights).

The following m₁ lines each contain two positive integers representing the arrival and departure times of a domestic flight.

The next m₂ lines each contain two positive integers representing the arrival and departure times of an international flight.

outputFormat

Output a single integer representing the maximum number of flights that can be served by a jet bridge under an optimal allocation.

sample

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

7