문제 설명

Marita의 동생이 거실 바닥에 장난감을 흩어 놓았습니다. 다행히도 Marita는 장난감을 치울 수 있는 특수 로봇을 설계했습니다. 그러나, 그녀는 어느 로봇이 어떤 장난감을 집을지 결정해야 합니다.

장난감은 총 $T$ 개가 있으며, 정수 $W[i]$ 는 이 장난감의 무게를 나타내고, 정수 $S[i]$ 는 이 장난감의 부피를 나타냅니다. 로봇에는 두 가지 유형이 있습니다: 약한 로봇과 작은 로봇.

• 약한 로봇이 $A$ 개 있습니다. 각 약한 로봇에는 무게 제한 $X[i]$ 이 있으며, 이는 해당 로봇이 무게가 $X[i]$ 미만인 장난감만 집을 수 있음을 의미하며, 장난감의 부피는 상관없습니다.
• 작은 로봇이 $B$ 개 있습니다. 각 작은 로봇에는 부피 제한 $Y[i]$ 이 있으며, 이는 해당 로봇이 부피가 $Y[i]$ 미만인 장난감만 집을 수 있음을 의미하며, 장난감의 무게는 상관없습니다.

각 로봇은 1분 동안 장난감을 집어 치울 수 있습니다. 서로 다른 로봇은 동시에 다른 장난감을 집어 치울 수 있습니다.

당신의 임무는 Marita의 로봇이 모든 장난감을 치울 수 있는지 여부를 결정하고, 그렇다면 최소 시간이 얼마나 걸릴지 계산하는 것입니다.

입력 형식

• 첫 번째 줄: $A$ 는 약한 로봇의 수, $B$ 는 작은 로봇의 수, $T$ 는 장난감의 수를 나타냅니다;
• 두 번째 줄: 길이가 $A$ 인 배열 $X[0],\cdots,X[A-1]$ 로, $X[i]$ 는 $i$ 번째 약한 로봇의 무게 제한을 나타냅니다;
• 세 번째 줄: 길이가 $B$ 인 배열 $Y[0],\cdots,Y[B-1]$ 로, $Y[i]$ 는 $i$ 번째 작은 로봇의 부피 제한을 나타냅니다;
• 다음 $T$ 줄: $W[i]$, $S[i]$ 로, $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

노트

$100\%$의 데이터에 대해, $1 \leq T \leq 10^6$, $0 \leq A,B \leq 5 \times 10^4$ 이고 $1 \leq A+B$, $1 \leq X[i],Y[i],W[i],S[i] \leq 2 \times 10^9$ 입니다.