題目描述

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。

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

範例輸出 #1

3

範例 #2

範例輸入 #2

2 1 3
2 5
2
3 1
5 3
2 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$。