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

다행히도 마리타는 장난감을 정리하는 특별한 로봇들을 개발하였다.

마리타는 어떤 로봇이 어떤 장난감을 집어야 하는지 결정하도록 당신에게 도움을 청했다.

장난감은 총 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짜리의 장난감을 정리할 수 없기 때문에, 모든 장난감들을 치우는 것은 불가능하다.

<제약조건>

⚫ 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

[서브태스크]

서브태스크 1 : T = 2 및 A + B = 2 (정확히 두 개의 장난감 및 두 개의 로봇)

서브태스크 2 : B = 0 (모든 로봇이 연약함)

서브태스크 3 : T ≤ 50 및 A + B ≤ 50

서브태스크 4 : T ≤ 10,000 및 A + B ≤ 1,000

서브태스크 5 : (없음)

robots timer 3s memory 256MB

robots 3s 256MB