나이가 든 존은 안타깝게도 점점 심술궂고 의심이 많아졌다. 다양한 소들이 자신의 농장을 크게 발전시키는 데 얼마나 많은 도움을 주었는지 잊은 존은 최근 농장 둘레에 거대한 울타리를 세웠다. 이 때문에 이웃 농장의 소들이 방문하기 어려워졌고, 몇몇 이웃 농장의 소들은 아예 들어올 수 없게 되었다.

여전히 존의 농장에 들어올 수 있는 이웃 소들도 이전보다 복잡한 절차를 거쳐야 한다. 농장으로 들어가는 문은 하나뿐이며, 각 소는 이 문에서 긴 질문에 답해야 한다. 이 때문에 소들이 긴 줄을 서는 일이 자주 생긴다.

농장을 방문하는 \(N\)마리의 소에 대하여, 각 소가 문에 도착하는 시각과 질문에 답하는 데 필요한 시간이 주어진다. 한 번에 한 마리의 소만 질문에 답할 수 있으므로 여러 소가 비슷한 시각에 도착하면 차례를 기다려야 할 수 있다.

예를 들어, 한 소가 시각 \(5\)에 도착하여 질문에 답하는 데 \(7\)의 시간이 필요하다면 시각 \(8\)에 도착한 다른 소는 시각 \(12\)까지 기다린 뒤 질문에 답하기 시작해야 한다.

모든 소가 질문에 답하고 농장에 들어갈 수 있는 가장 이른 시각을 구하여라.

입력

첫째 줄에 농장을 방문하는 소의 수 \(N\)이 주어진다.

다음 \(N\)개의 줄에 각 소가 도착하는 시각 \(a_i\)와 질문에 답하는 데 필요한 시간 \(t_i\)가 공백으로 구분되어 주어진다.

출력

모든 소가 질문에 답하고 농장에 들어갈 수 있는 가장 이른 시각을 출력한다.

제한 사항

• \(1 \le N \le 100\)
• \(1 \le a_i,t_i \le 1,000,000\)

예제 입력 1

3
2 1
8 3
5 7

예제 출력 1

15

예제 설명 1

첫 번째 소는 시각 \(2\)에 도착하여 빠르게 질문에 답한다. 문은 세 번째 소가 시각 \(5\)에 도착할 때까지 잠시 비어 있다.

세 번째 소가 시각 \(5\)부터 질문에 답하는 동안 두 번째 소가 시각 \(8\)에 도착한다. 두 번째 소는 시각 \(5+7=12\)까지 기다린 뒤 질문에 답하기 시작하여 시각 \(12+3=15\)에 끝낸다.

출처

USACO 2017 February Contest, Bronze, Problem 3. Why Did the Cow Cross the Road III