소는 왜 길을 건넜을까 III

농부 존은 나이가 들면서 안타깝게도 점점 더 심술궂고 편집증적으로 변했다. 소들의 다양성이 오랜 세월 농장을 얼마나 번창하게 해 주었는지 잊어버린 그는, 최근 농장 둘레에 거대한 울타리를 세워 이웃 농장의 소들이 방문하는 것을 막고, 몇몇 이웃 농장의 출입은 완전히 금지하기로 했다. 소들은 이 상황에 몹시 화가 났는데, 친구들을 더 이상 만날 수 없기 때문만이 아니라, 이 때문에 1년 내내 손꼽아 기다리던 국제 착유 올림피아드 참가를 취소해야 했기 때문이다.

아직 농부 존의 농장에 들어갈 수 있는 이웃 소들도 절차가 더 번거로워졌다는 것을 알게 되었다. 이제는 단 하나의 문을 통해서만 들어갈 수 있고, 문에서 각 소는 강도 높은 심문을 받아야 해서 소들이 긴 줄을 서게 되는 일이 잦다.

농장을 방문하는 \(N\)마리의 소 각각에 대해, 그 소가 문에 도착하는 시각과 입장 심문에 답하는 데 걸리는 시간이 주어진다. 한 번에 한 마리의 소만 심문을 받을 수 있으므로, 여러 소가 비슷한 시각에 도착하면 줄을 서서 한 마리씩 차례로 처리되기를 기다려야 할 가능성이 높다. 예를 들어 어떤 소가 시각 5에 도착해 7 단위 시간 동안 심문에 답한다면, 시각 8에 도착한 다른 소는 시각 12까지 기다려야 심문에 답하기 시작할 수 있다.

모든 소가 농장에 들어갈 수 있는 가장 이른 시각을 구하시오.

문제 출처: Brian Dean

문제 출처: Brian Dean

입력의 첫째 줄에 100 이하의 양의 정수 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 소가 한 마리씩 주어지며, 도착 시각과 심문에 필요한 시간이 주어진다. 이 수들은 각각 1,000,000 이하의 양의 정수이다.

모든 소의 처리가 완료될 수 있는 가장 이른 시각을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Bronze