과일노리

재훈이는 과일노리에서 영화를 보는 걸 좋아한다. 그런데 어느 날 사이버안전지킴이 병희가 만든 학인봇이 나타나 과일노리 접속을 차단하기 시작했다. 학인봇은 트래픽이 오가는 길목에 일정한 간격으로 나타나 몇 초 동안 침입자를 탐지한다. 영화가 너무 보고 싶은 재훈이는 학인봇을 피해 과일노리에 접속하려고 한다.

다음 예시를 보자.

예시에서 재훈이는 과일노리에 접속하려면 구간 4개를 차례로 지나야 한다. 구간에 적힌 A/B는 그 구간의 학인봇이 B초 동안 침입자를 탐지하고 사라진 뒤 A초 동안 쉬는 일을 반복한다는 뜻이다. 즉 학인봇은 A초 간격으로 나타나고, 한 번 나타나면 B초 동안 활동한다. 침입자가 나타나는 순간(0초)에 모든 구간의 학인봇이 한꺼번에 나타나 활동을 시작한다.

재훈이는 경로 중간의 네트워크 장비에 숨어 기다리면서 이동해야 한다. 어떤 구간의 출발 지점에 있을 때 그 구간의 학인봇이 활동 중이면 재훈이는 그 구간으로 출발할 수 없고, 학인봇이 사라질 때까지 기다려야 한다. 학인봇이 쉬는 동안에는 바로 출발할 수 있다. 구간 하나를 지나는 데에는 1초가 걸린다.

예시를 따라가 보면 다음과 같다.

• 재훈이의 핸드폰(0초): 학인봇이 막 나타났으므로 5초 기다린 뒤 다음 구간으로 이동한다.
• 첫 번째 스위치(6초): 학인봇이 쉬는 시간이므로 기다리지 않고 바로 이동한다.
• 두 번째 라우터(7초): 학인봇의 활동이 2초 남았으므로 2초 기다린 뒤 이동한다.
• 세 번째 서버(10초): 학인봇의 활동이 4초 남았으므로 4초 기다린 뒤 이동한다.

따라서 예시에서 재훈이가 과일노리에 접속하는 데 걸리는 시간은 최소 15초이다.

심술쟁이 해커 임준오(동탄 주민)는 재훈이를 경찰에 신고해서 윤리의식을 일깨워 주려고 한다. 준오가 112에 전화를 거는 동안 재훈이의 최소 접속 시간을 구해서 준오에게 알려 주자.

첫째 줄에 재훈이가 지나야 하는 구간의 수 $N$이 주어진다. ($1 \le N \le 50{,}000$)

다음 $N$개의 줄에는 $i$번째 구간에 있는 학인봇의 활동 정보 $a$, $b$가 공백으로 구분되어 주어진다. 이 학인봇은 $a$초 간격으로 나타나고, 나타나면 $b$초 동안 활동한 뒤 사라진다. ($1 \le a, b \le 1{,}000$)

재훈이가 과일노리에 접속하는 데 필요한 최소 시간(초)을 출력한다.