재료 최적화 timer 5s memory 1024MB

하타이(Hathai)는 자신의 케이터링 서비스가 동네에서 가장 신선한 음식을 제공한다는 점을 자랑스러워한다. 이를 위해 방부제가 없는 신선한 재료를 계속해서 배송받는다. 하지만 그만큼 재료가 상하지 않도록 관리하는 것이 큰 도전이 된다. 하타이의 현재 특선 메뉴는 특별히 관리해야 하는 태국 바질 잎을 정확히 \mathbf{U}장 사용한다.

하타이는 태국 바질 배송 일정표를 가지고 있다. i번째 배송은(오픈 시간으로부터 지난 분 단위의 시간인) \mathbf{M_i}의 시작 시점에 도착하며, 태국 바질 잎을 정확히 \mathbf{L_i}장 가져온다. 이 잎들은 도착한 뒤 최대 \mathbf{E_i}분 동안만 보관할 수 있다. 하타이는 특선 요리를 준비해야 하는 주문 시각 \mathbf{O_1}, \mathbf{O_2}, \dots, \mathbf{O_N}을 알고 있다. 주문 i는 시각 \mathbf{O_i}에 상하지 않은 태국 바질 잎이 \mathbf{U}장 있어야만 처리할 수 있다. 잎이 주문이 들어오는 시각에 정확히 상하게 된다면, 그 잎은 해당 주문을 처리하는 데 사용할 수 없다는 점에 유의하라. 주문을 처리하면 사용 가능한 잎들 중 \mathbf{U}장을 사용해야 하며, 사용한 잎은 이후 주문에 사용할 수 없다. 하타이가 처리할 수 없는 주문을 한 번이라도 받게 되면, 남은 모든 주문은 취소된다. 하타이는 주방을 닫고 주문 처리 일정을 어떻게 개선할지 고민해야 하기 때문이다.

예를 들어 하타이의 배송 일정이 다음 4개 배송으로 이루어져 있다고 하자:

• 도착 시간: 1. 수량: 10. 상하기까지 남은 시간: 2.
• 도착 시간: 3. 수량: 4. 상하기까지 남은 시간: 2.
• 도착 시간: 5. 수량: 1. 상하기까지 남은 시간: 4.
• 도착 시간: 10. 수량: 6. 상하기까지 남은 시간: 3.

또한 주문이 시각 3, 4, 6, 10에 총 4개 들어온다고 하자. 이 예시에서는 주문 하나를 처리할 때마다 \mathbf{U}=2장의 잎이 필요하다.

첫 번째 배송은 시각 3에 상해 버리므로, 어떤 주문에도 사용할 수 없다. 그 다음 시각 3과 4에 들어온 첫 번째/두 번째 주문은 두 번째 배송에서 온 잎 4장을 사용해 처리할 수 있다. 세 번째 주문이 들어오는 시각 6에는 보관 중인 잎이 1장뿐이므로, 하타이는 이 주문을 처리할 수 없다. 또한 시각 10에 배송이 있더라도, 하타이는 이미 주방을 닫았으므로 시각 10의 네 번째 주문 역시 처리할 수 없다. 이 예시에서 하타이가 처리한 주문의 총 개수는 2개이다.

배송 일정과 주문 일정이 주어질 때, 태국 바질 잎의 사용을 최적으로 계획하면 하타이가 처리할 수 있는 주문의 최대 개수는 얼마인가?