소가 길을 건너간 이유 3
시간 제한2초메모리 제한512 MB
소마다 도착 시각과 검사 시간이 주어질 때, 도착 순서대로 한 마리씩 검사할 때 모든 소가 입장을 마치는 시각을 구한다.
문제
이웃 농장의 소가 길을 마구잡이로 건너는 데 진절머리가 난 존은 극단적인 결정을 내렸다. 농장 둘레에 아주 큰 울타리를 치기로 한 것이다. 이렇게 하면 근처 농장의 소가 들어올 일은 거의 없다. 주변 소들은 이 일로 몹시 분개했다. 친구네 집에 놀러 갈 수 없게 되었을 뿐 아니라, 해마다 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.
이웃 농장의 소 가운데 존의 농장을 방문할 수 있는 소가 조금 있긴 하지만 이 소들도 마음을 놓을 수는 없다. 존의 농장으로 들어가는 문은 하나뿐이고, 그 문을 지나려면 감시관에게 길고 긴 검문을 받아야 한다. 여러 마리의 소가 한꺼번에 들어가려고 하면 그만큼 줄이 길어진다.
마리의 소가 이 농장을 방문하러 왔다. 도착 시각과 검문에 걸리는 시간은 소마다 다르다(물론 같을 수도 있다). 두 소가 동시에 검문을 받을 수는 없다. 예를 들어 어떤 소가 5초에 도착해서 7초 동안 검문을 받으면, 8초에 도착한 다음 소는 12초까지 줄을 서 있다가 검문을 받는다.
모든 소가 농장에 들어가기까지 얼마나 걸리는지 구하시오.
입력
첫째 줄에 소의 수 이 주어진다. 은 100 이하의 양의 정수이다.
다음 개의 줄에는 한 줄에 한 마리씩 소의 도착 시각과 검문 시간이 공백으로 구분되어 주어진다. 두 값 모두 1,000,000 이하의 양의 정수이다.
출력
모든 소가 농장에 들어가는 시각의 최솟값을 출력한다. 시각은 0초부터 센다.
힌트
예제에서 첫 번째 소는 2초에 도착해서 3초에 농장에 들어간다. 그다음 세 번째 소가 5초에 도착해서 12초에 농장에 들어간다. 마지막으로 두 번째 소는 8초에 도착하지만 세 번째 소가 검문을 받고 있으므로 12초까지 기다렸다가 15초에 농장에 들어간다.