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)
0 1000 65536
1 1000 65536
2 2000 65536
3 5000 65536
4 1000 65536
5 5000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536
10 2000 65536
11 5000 65536
12 1000 65536
13 5000 65536
14 5000 65536
15 5000 65536
16 2000 65536
17 5000 65536
18 2000 65536