문제
마리타의 남동생은 모든 장난감을 거실 바닥에 어질러놓았다!
다행히도 마리타는 장난감을 정리하는 특별한 로봇들을 개발하였다.
마리타는 어떤 로봇이 어떤 장난감을 집어야 하는지 결정하도록 당신에게 도움을 청했다.
장난감은 총 T 개가 있으며, 각각은 정수 무게 W[i] 와 정수 크기 S[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짜리의 장난감을 정리할 수 없기 때문에, 모든 장난감들을 치우는 것은 불가능하다.
입력
line 1: 연약한 로봇의 수 A, 작은 로봇의 수 B, 장난감의 개수 T가 공백으로 구분하여 들어온다.
line 2: 연약한 로봇의 무게 제한이 A개 들어온다. (X[0] … X[A-1])
line 3: 작은 로봇의 크기 제한이 B개 들어온다. (Y[0] … Y[B-1])
이상 lines : 장난감의 무게 W, 크기 S가 공백으로 구분하여 들어온다.
출력
출력의 첫 줄에 모든 장난감을 정리하는 데 걸리는 가장 짧은 시간을 출력한다.
불가능한 경우 –1을 출력한다.
예제1
3210
629
47
46
85
23
79
18
51
33
87
76
105
3
예제2
213
25
2
31
53
22
-1