카페 주문표 다시 꽂기

문제

한 카페의 주문 기록 장치에 잠시 문제가 생겨 주문표가 도착 시각과 관계없는 순서로 출력되었다. 직원은 출력된 주문표에 위에서부터 1번부터 N번까지 번호를 붙였다. 각 주문표에는 주문이 실제로 도착한 시각과 그 주문의 음료를 만드는 데 필요한 시간이 적혀 있다. 모든 시각과 시간은 영업 시작 시각을 0으로 하는 정수 단위로 표현한다. 카페에는 음료를 만드는 직원이 한 명 있으며, 한 번에 주문 하나만 만들 수 있다. 직원은 실제 도착 시각이 빠른 주문부터 처리한다. 도착 시각이 같은 주문이 여러 개면 주문표 번호가 작은 주문부터 처리한다. 따라서 입력에 나중에 등장한 주문이 먼저 처리될 수도 있지만, 도착 시각까지 같다면 입력에 먼저 등장한 주문이 앞선다. 직원은 시각 0부터 일할 수 있다. 앞선 주문을 모두 마친 시각에 다음 주문이 이미 도착해 있으면 쉬지 않고 바로 만들기 시작한다. 다음 주문이 아직 도착하지 않았다면 그 주문이 도착할 때까지 기다린다. 주문 하나를 만들기 시작하면 해당 주문표에 적힌 시간 동안 중단 없이 작업하며, 작업이 끝나는 시각에 다음 주문을 시작할 수 있다. 도착 시각과 앞선 주문의 완료 시각이 같아도 추가로 기다릴 필요는 없다. 어떤 주문의 대기 시간은 그 주문을 만들기 시작한 시각에서 실제 도착 시각을 뺀 값이다. 음료를 만드는 시간은 대기 시간에 포함하지 않는다. 직원은 정해진 순서를 바꾸거나 여러 주문을 합쳐 만들지 않는다. 모든 주문을 처리했을 때 가장 긴 대기 시간과 마지막 주문을 완성한 시각을 구한다. 모든 주문이 도착하자마자 처리되었다면 가장 긴 대기 시간은 0이다.

입력

첫째 줄에 주문 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
다음 N개의 줄 중 i번째 줄에 i번 주문표의 실제 도착 시각 t_i와 작업 시간 d_i가 공백으로 구분되어 주어진다. t_i와 d_i는 정수이며, 0 ≤ t_i ≤ 9,999, 1 ≤ d_i ≤ 9이다.

출력

가장 긴 대기 시간과 마지막 주문을 완성한 시각을 공백으로 구분하여 한 줄에 출력한다.

4
5 2
0 4
5 1
2 3

4 10

3
7 3
7 1
7 2

4 13

3
9 1
0 2
4 3

0 10

출처: Devin.KR 자체 제작