1815 . [IOI 2013] 機器人 Robots
TopCoder
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 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
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 1
3
Hints
鴨子的小弟弟居然是螺旋狀的=)
Problem Source
IOI 2013
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~18 | 100 |