Problem Description

Marita's younger brother has scattered toys all over the living room floor. Fortunately, Marita has designed a special robot that can clean up the toys. However, she needs to determine which robot should pick up which toy.

There are $T$ toys, with integer $W[i]$ representing the weight of the toy and integer $S[i]$ representing the volume of the toy. There are two types of robots: weak robots and small robots.

• There are $A$ weak robots. Each weak robot has a weight limit $X[i]$, and it can only pick up toys with a weight strictly less than $X[i]$, regardless of the toy's volume.
• There are $B$ small robots. Each small robot has a volume limit $Y[i]$, and it can only pick up toys with a volume strictly less than $Y[i]$, regardless of the toy's weight.

Each of Marita's robots takes 1 minute to pick up and put away one toy. Different robots can pick up and put away different toys simultaneously.

Your task is to determine if Marita's robots can clean up all the toys. If they can, you need to find out the minimum time required to do so.

Input Format

• Line 1: $A$, the number of weak robots, $B$, the number of small robots, and $T$, the number of toys.
• Line 2: An array of length $A$, $X[0], \cdots, X[A-1]$, where $X[i]$ represents the weight limit of the $i$-th weak robot.
• Line 3: An array of length $B$, $Y[0], \cdots, Y[B-1]$, where $Y[i]$ represents the volume limit of the $i$-th small robot.
• The next $T$ lines: $W[i]$ and $S[i]$, where $W[i]$ represents the weight of the $i$-th toy and $S[i]$ represents the volume of the $i$-th toy.

If $A = 0$ or $B = 0$, the corresponding line (either the second or the third line) will be empty.

Output Format

• A single line, output the minimum time required for the robots to clean up all the toys. If it is not possible to clean up all the toys, output -1.

Sample Input and Output

Input Sample #1

3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5

Output Sample #1

3

Input Sample #2

2 1 3
2 5
2
3 1
5 3
2 2

Output Sample #2

-1

Notes/Hints

For $100\%$ of the data, $1 \le T \le 10^6$, $0 \le A, B \le 5 \times 10^4$ and $1 \le A + B$, $1 \le X[i], Y[i], W[i], S[i] \le 2 \times 10^9$.

见题面 Input 部分

见题面 Output 部分