TopCoder

User's AC Ratio

87.5% (14/16)

Submission's AC Ratio

27.3% (18/66)

Tags

Description

鴨子的小弟弟竟然把玩具丟得滿地都是!所幸鴨子發展了一些可以把玩具收好的特殊機器人。鴨子需要你的幫助來決定哪一架機器人應該撿起並收好哪一些玩具。

房間內有T 個玩具,每個玩具的重量為Wi,體積大小為Si。機器人有兩種:弱雞型(weak)與小不點型(small)。
  總共有A 架弱雞型機器人。每架弱雞型機器人可拿起重量小於Xi的玩具。玩具的大小可以忽視。
  總共有B 架小不點型機器人,每架小不點型機器人可塞入體積小於Yi的玩具。玩具的重量可以忽視。
鴨子的每一架機器人需要花掉1分鐘(Minute)的時間才能收納一個玩具。同時間不同機器人可以各自收納不同的玩具。

你的任務是決定鴨子的機器人是否可以把玩具全部收納完。如果可以,請計算出把玩具收納完成所需要的最短時間。

Input Format

第一行: A B T,分別表示弱雞型(weak), 小不點型(small), 玩具的個數。
第二行: X0, X1, … ,XA-1,Xi表示第i個弱雞型機器人可拿起重量小於Xi的玩具。
第三行: Y0, Y1, … ,YB-1,Yi表示第i個小不點型機器人可拿起體積小於Yi的玩具。
然後是T行:Wi Si,表示第i個玩具的重量與體積。

•1 ≤ T ≤ 1,000,000
•0 ≤ A, B ≤ 50,000 and 1 ≤ A + B
•1 ≤ Xi, Yi, Wi, Si ≤ 2,000,000,000

Output Format

輸出將所有玩具收納完成所需的最小時間(分鐘)。

如果無法收納完成,則輸出-1 。

Sample Input

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

Sample Output

3

Hints

鴨子的小弟弟居然是螺旋狀的=)

Problem Source

IOI 2013

Subtasks

For Testdata: 0 ~ 18, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 2000 65536 262144
3 5000 65536 262144
4 1000 65536 262144
5 5000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 2000 65536 262144
11 5000 65536 262144
12 1000 65536 262144
13 5000 65536 262144
14 5000 65536 262144
15 5000 65536 262144
16 2000 65536 262144
17 5000 65536 262144
18 2000 65536 262144