Problem Description

Marita’s younger brother has thrown toys all over the living room floor, making a big mess. Luckily, Marita has designed special robots that can put the toys away. However, she needs to decide which robot should pick up which toy.

There are $T$ toys. Integer $W[i]$ represents the weight of the $i$-th toy, and integer $S[i]$ represents the volume of the $i$-th toy. There are two kinds of robots: weak robots and small robots.

• There are $A$ weak robots. Each weak robot has a weight limit $X[i]$. It can only pick up toys with 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]$. It can only pick up toys with volume strictly less than $Y[i]$, regardless of the toy’s weight.

Each of Marita’s robots takes $1$ minute to carry one toy away and put it in place. Different robots can carry away and put away different toys at the same time.

Your task is to determine whether Marita’s robots can put away all the toys. If yes, find the minimum time needed.

Input Format

• Line 1: $A$ is the number of weak robots, $B$ is the number of small robots, and $T$ is the number of toys.

• Line 2: An array of length $A$, $X[0],\cdots,X[A-1]$. For $0 \le i \le A-1$, $X[i]$ is the weight limit of the $i$-th weak robot.

• Line 3: An array of length $B$, $Y[0],\cdots,Y[B-1]$. For $0 \le i \le B-1$, $Y[i]$ is the volume limit of the $i$-th small robot.

• The next $T$ lines: $W[i]$, $S[i]$. For $1 \le i \le T$, $W[i]$ is the weight of the $i$-th toy, and $S[i]$ is the volume of the $i$-th toy.

• If $A = 0$ or $B = 0$, then the corresponding line (line 2 or line 3) is empty.

Output Format

• One line. Output the minimum time needed for the robots to put away all toys. If it is impossible to put away all toys, output -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

3

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

-1

Hint

For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5