Problem : 291 - Robots

Problem Statistics

Solved Member: 35　　Submission: 376　　User Tried: 36

Statement:

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

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

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

Input:Output:

第一行： A B T，分別表示弱雞型(weak), 小不點型(small), 玩具的個數。
第二行： X₀, X₁, … ,X_A-1，X_i表示第i個弱雞型機器人可拿起重量小於X_i的玩具。
第三行： Y₀, Y₁, … ,Y_B-1，Y_i表示第i個小不點型機器人可拿起體積小於Y_i的玩具。
然後是T行：W_i S_i，表示第i個玩具的重量與體積。

•1 ≤ T ≤ 1,000,000
•0 ≤ A, B ≤ 50,000 and 1 ≤ A + B
•1 ≤ X_i, Y_i, W_i, S_i ≤ 2,000,000,000

子任務	分數	額外輸入限制
1	14	T = 2 和 A + B = 2 (剛好2個玩具與兩隻機器人)
2	14	B = 0 (所有機器人都是弱雞型)
3	25	T ≤ 50 和 A + B ≤ 50
4	37	T ≤ 10,000 和 A + B ≤ 1,000
5	10	(無)

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

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

Sample Input:Sample Output:

Sample #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

Sample #2:
2 1 3
2 5
2
3 1
5 3
2 2

Sample #1:
3

Sample #2:
-1

HINT:

Sample #1:

玩具編號	0	1	2	3	4	5	6	7	8	9
重量	4	8	2	7	1	5	3	8	7	10
體積	6	5	3	9	8	1	3	7	6	5

將所有玩具收納完成所需要最短的時間是3分鐘：

	弱雞型機器人0	弱雞型機器人1	弱雞型機器人2	小不點型型機器人0	小不點型型機器人1
第1分鐘	Toy 0	Toy 4	Toy 1	Toy 6	Toy 2
第2分鐘	Toy 5		Toy 3		Toy 8
第3分鐘			Toy 7		Toy 9

Sample #2:

玩具編號	0	1	2
重量	3	5	2
體積	1	3	2

沒有機器人可以撿起重量為5和體積為3的玩具，故在這Sample中機器人無法將所有玩具收納完成。

Source:

IOI 2013

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1-1	1000ms	65536kb	14
1-2	1000ms	65536kb
1-3	1000ms	65536kb
1-4	1000ms	65536kb
1-5	1000ms	65536kb
1-6	1000ms	65536kb
1-7	1000ms	65536kb
2-1	5000ms	65536kb	14
2-2	2000ms	65536kb
2-3	2000ms	65536kb
2-4	5000ms	65536kb
2-5	5000ms	65536kb
3-1	1000ms	65536kb	25
3-2	1000ms	65536kb
3-3	1000ms	65536kb
3-4	1000ms	65536kb
3-5	1000ms	65536kb
3-6	1000ms	65536kb
4-1	1000ms	65536kb	37
4-2	1000ms	65536kb
4-3	1000ms	65536kb
5-1	5000ms	65536kb	10
5-2	5000ms	65536kb
5-3	5000ms	65536kb
5-4	5000ms	65536kb
5-5	5000ms	65536kb
5-6	5000ms	65536kb
5-7	5000ms	65536kb
5-8	5000ms	65536kb