robots

프로그램 명: ioi_robo

제한시간: 3 초

마리타의 남동생은 모든 장난감을 거실 바닥에 어질러놓았다!

다행히도 마리타는 장난감을 정리하는 특별한 로봇들을 개발하였다. 마리타는 어떤 로봇이 어떤 장난감을 집어야 하는지 결정하도록 당신에게 도움을 청했다.

장난감은 총 T 개가 있으며, 각각은 정수 무게 W[i] 와 정수 크기 S[i] 를 가진다. 로봇들은 연약한 로봇과 작은 로봇 두 가지 종류가 있다.

연약한 로봇은 총 A 개가 있다.: 각 연약한 로봇에는 무게 제한 X[i] 가 있어서, X[i] 미만의 무게를 가진 장난감만을 운반할 수 있다. 장난감의 크기는 상관없다.
작은 로봇은 총 B 개가 있다.: 각 작은 로봇에는 크기 제한 Y[i] 가 있어서, Y[i] 미만의 크기를 가진 장난감만을 운반할 수 있다. 장난감의 무게는 상관없다.

마리타의 로봇들 각각은 하나의 장난감을 정리하는 데 1분이 걸린다. 여러 로봇들이 서로 다른 장난감들을 동시에 정리할 수 있다.

당신의 임무는 마리타의 로봇들이 모든 장난감들을 정리할 수 있는지 결정하고, 만약 가능하다면, 모든 장난감을 정리하는데 걸리는 가장 짧은 시간을 찾는 것이다.

첫 번째 예시로, 무게 제한 X = [6, 2, 9] 를 가진 A = 3 개의 연약한 로봇과 크기 제한 Y = [4, 7] 을 가진 B = 2 개의 작은 로봇이 있고, T = 10 개의 장난감이 아래와 같이 있다고 하자:

장난감 번호 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 분째 장난감 0 장난감 4 장난감1 장난감6 장난감2

2 분째 장난감 5 장난감 3 장난감 8

3 분째 장난감 7 장난감 9

두 번째 예시로, 무게 제한 X = [2, 5] 를 가진 A = 2 개의 연약한 로봇과 크기 제한 Y = [2] 를 가진 B = 1 개의 작은 로봇이 있고, T = 3 개의 장난감이 아래와 같이 있다고 하자:

장난감번호 0 1 2

무게 3 5 2

크기 1 3 2

어떤 로봇도 무게 5, 크기 3짜리의 장난감을 정리할 수 없기 때문에, 모든 장난감 들을 치우는 것은 불가능하다.

첫 줄에는 연약할 로봇의 개수 A , 작은 로봇의 개수 T , 장난감의 개수 T 가 주어진다. 1 ≤ T ≤ 1,000,000 , 0 ≤ A, B ≤ 50,000 및 1 ≤ A + B
다음 줄에는 무게 제한 Xi 가 A 개의 수
다음 줄에는 크기 제한 Yi 가 T 개의 수
다음 T 줄에는 각 장난감의 무게 Wi 와 크기 Xi 가 차례대로 주어진다.

(1 ≤ X[i], Y[i], W[i], S[i] ≤ 2,000,000,000)

모든 장난감을 정리하는데 걸리는 가장 짧은 시간(분)을 출력한다. 만약, 정리하는 것이 불가능하다면 -1 을 출력한다.

출처:ioi 2013