You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$。