복사실 작업 일정
시간 제한2초메모리 제한512 MB
마감 시각과 분량이 주문마다 주어지고 주문이 하나씩 추가될 때, 한 대의 기계에서 선점 스케줄이 가능하다고 할 때 최대 지연 시간을 최소로 만든 값을 매번 구한다.
문제
Senobar는 학생이며 낮에 대학 복사실에서 일한다. 대학 복사실에는 교수와 학생의 주문이 많이 들어온다.
그녀는 매일 다음 날 처리할 주문을 받고, 각 주문에 대해 접수 시각, 주문량(1000장 단위), 고객이 정한 마감 시각을 기록한다. 그리고 다음 날 12:00부터 작업을 시작한다.
그녀는 고객을 위해 최선을 다하고 싶지만, 주문량이 복사기의 처리 능력을 넘을 때가 있다. 따라서 고객이 정한 마감 시각을 항상 지킬 수는 없으며, 어떤 주문의 완료 시각이 마감 시각을 넘는 최대 시간을 최소화하는 최선의 일정을 고민한다. 그녀가 주문 일정을 짜도록 도와라. 복사기의 용지함 용량은 1000장이고, 이는 1시간에 복사한다. 또한 한 주문을 한 번에 연속해서 처리할 필요는 없다. 주문 A를 한 단위(1000장) 처리한 뒤 다른 주문을 몇 단위 처리하고, 다시 주문 A로 돌아와도 된다.
입력
첫째 줄에는 주문의 수 T가 주어진다. 다음 T개 줄에는 각각 두 정수 D와 U가 주어지며, 이는 각 주문의 마감 시각(오후)과 페이지 수(단위: 1000장)이다.
출력
출력은 T개 줄로, 주문 목록의 첫 i개 주문을 최적으로 처리했을 때 어떤 주문의 완료 시각이 마감 시각을 넘는 최대 시간을 각 줄에 출력한다. 자세한 내용은 예제 입력을 참고하라.
제한
- 1 ≤ T ≤ 10^5
- 1 ≤ Ui ≤ 10^3
힌트
첫 번째 주문만 처리하면 2시간 만에 끝낼 수 있으므로 마감 시각을 넘기지 않는다.
처음 두 주문에 대한 최적 일정은 다음과 같다.
- time 1: 주문 2
- time 2: 주문 1
- time 3: 주문 1
주문 1을 1시간 넘겼으므로 1을 반환한다.
처음 세 주문에 대한 최적 일정은 다음과 같다.
- time 1: 주문 2
- time 2: 주문 1
- time 3: 주문 3
- time 4: 주문 1
- time 5: 주문 3
- time 6: 주문 3
주문 1의 마감 시각은 2이고 time 4에 끝난다. 따라서 마감 시각을 2만큼 넘긴다. 주문 2의 마감 시각은 1이고 time 1에 끝나므로 마감 시각을 0만큼 넘긴다. 주문 3의 마감 시각은 4이고 time 6에 끝나므로 마감 시각을 2만큼 넘긴다.
따라서 마감 시각을 넘긴 최대 시간은 2이다. 어떤 일정도 이보다 잘할 수 없다. 주문이 5개인 경우에도 비슷하게 계산할 수 있다.