题目描述

Marita 的弟弟把玩具扔在客厅地板上，乱七八糟。庆幸的是，Marita 设计了一种特殊的机器人可以收拾玩具。 不过，她需要确定哪个机器人去拣起哪个玩具。

一共有 $T$ 个玩具,整数 $W[i]$ 表示这个玩具的重量，整数 $S[i]$ 表示这个玩具的体积。机器人有两种，分别是：弱机器人和小机器人。

• 有 $A$ 个弱机器人。每个弱机器人有一个重量限制 $X[i]$，它只能拿起重量严格小于 $X[i]$ 的玩具，与玩具的体积大小没关系。
• 有 $B$ 个小机器人。每个小机器人有一个体积限制 $Y[i]$，它只能拿起体积严格小于 $Y[i]$ 的玩具，与玩具的重量大小没有关系。

Marita 的每个机器人用 $1$ 分钟将一个玩具拿走放好。不同的机器人可以同时拿走并放好不同的玩具。

你的任务是确定 Marita 的机器人是否可以将所有的玩具都收拾好，如果是，那么最少用多少时间可以收拾好。

输入格式

• 第1行: $A$ 表示弱机器人的数目，$B$ 表示小机器人的数目，$T$ 表示玩具的数目；

• 第2行: 长度为 $A$ 的数组 $X[0],\cdots,X[A­-1]$，对于 $0 \le i \le A-1$，$X[i]$ 表示第 $i$ 个弱机器人的重量限制；

• 第3行: 长度为 $B$ 的数组 $Y[0],\cdots,Y[B-­1]$，对于 $1 \le i \le B-1$，$Y[i]$ 表示第 $i$ 个小机器人的体积限制；

• 接下来 $T$ 行: $W[i]$，$S[i]$，对于 $1 \le i \le T$，$W[i]$ 代表第 $i$ 个玩具的重量，$S[i]$ 代表第 $i$ 个玩具的体积。

• 如果 $A = 0$ 或者 $B = 0$ ，那么相应的行（第 $2$ 行或者第 $3$ 行）为空。

输出格式

• 共 $1$ 行，输出机器人收拾好所有玩具所需要的最短时间，如果无法收拾好所有玩具，输出 ­-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

提示

对于 $100\%$ 的数据，$1 \le T \le 10^6$，$0 \le A,B \le 5 \times 10^4$ 且 $1 \le A+B$，$1 \le X[i],Y[i],W[i],S[i] \le 2 \times 10^9$。