题目描述

一共有 $n$ 件对数，每对数用 $(a,b)$ 表示 。 你有两类集合，每类都有若干个，你需要将每对数都放入一个集合中。 对于第一类集合，只能放入 $a$ 严格小于 $x_i$ 的数。 对于第二类集合，只能放入 $b$ 严格小于 $y_i$ 的数。

现在有 $A$ 个第一类集合（如果$a<x_i,(a,b)$就可以放入第一类集合 $i$);

以及 $B$ 个第二类集合（如果$b<y_i,(a,b)$就可以放入第二类集合 $i$ )

你需要将每个数对都放入一个集合中并且使得大小最大的集合最小。 如果不能放入所有数，输出 $-1$。

输入格式

第一行输入三个整数 $A,B,n$。 下一行输入 $A$ 个整数表示 $x_i$。 下一行输入 $B$ 个整数表示 $y_i$。 接下来 $n$ 行每行两个整数，表示第 $i$ 对数的 $a$ 和 $b$。

输出格式

最大集合的大小（数对个数）最小值。

样例 #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

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

-1

提示

样例1说明

一种方法：

第一类集合：(5 1) (4 6)放入集合1($x_1=6$)；（1 8）放入集合2($x_2=2$)；（8 5）（7 9）（8 7）放入集合3($x_3=9$)。

第二类集合：（2 3）放入集合1($y_1=4$)；（3,3）（7 6）（10 5）放入集合2($y_2=7$)。

样例2说明

（5 3）没有集合可放。

数据范围

• 对于 $20\%$ 的数据，有 $n=2,A+B=2$；
• 对于另外 $20\%$ 的数据，有 $B=0$；
• 对于另外 $20\%$ 的数据，有 $n\le 100,A+B\le 100$ ；
• 对于另外 $30\%$ 的数据，有 $n\le 10^4,A+B\le 10^3$；
• 对于全部 $100\%$ 的数据，有 $1\le n\le 10^6,0\le A,B\le 5\times 10^4,1\le A+B,1\le x_i,y_i,a_i,b_i\le 2\times 10^9$ 。