8875번 - 장난감 정리 로봇 서브태스크

마리타의 남동생은 모든 장난감을 거실 바닥에 어질러놓았다! 다행히도 마리타는 장난감을 정리하는 특별한 로봇들을 개발하였다. 마리타는 어떤 로봇이 어떤 장난감을 집어야 하는지 결정하도록 당신에게 도움을 청했다.

장난감은 총 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 개의 장난감이 아래와 같이 있다고 하자:

모든 장난감들을 정리하는 데 걸리는 가장 짧은 시간은 3분이다:

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

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

첫째 줄에 연약한 로봇의 개수 A, 작은 로봇의 개수 B, 장난감의 개수 T가 주어진다.

둘째 줄에는 각 연약한 로봇의 무게 제한을 나타내는 길이가 A인 배열이 주어진다.

셋째 줄에는 각 작은 로봇의 크기 제한을 나타나는 길이가 B인 배열이 주어진다.

다음 T개 줄에는 각 장난감의 무게 W[i]와 크기 S[i]가 주어진다.

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

• 1 ≤ T ≤ 1,000,000
• 0 ≤ A, B ≤ 50,000, 1 ≤ A+B
• 1 ≤ X[i], Y[i], W[i], S[i] ≤ 2,000,000,000
• 만약 A=0 또는 B=0이라면, 해당하는(두 번째 또는 세 번째)줄은 비어있다.