TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

87.5% (21/24)

Submission's AC Ratio

18.2% (29/159)

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

No. Testdata Range Score
1 0~18 100

Testdata and Limits

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