14493번 - 과일노리

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

아래의 예시를 보자.

재훈이는 과일노리에 접속하기 위해 총 4개의 구간을 거쳐야 한다. A/B는 해당 구간에서 학인봇이 A초 간격으로 나타나, B초 동안 침입자를 탐지하고 사라진다는 의미이다. 학인봇은 침입자 발생과 동시에 모든 구간에서 한꺼번에 나타나 활동을 시작한다. 따라서 재훈이는 학인봇의 감시를 피해 경로 중간의 네트워크 장비에 숨으면서 이동해야한다. 각 구간을 통과하는 데에는 1초의 시간이 소요된다. 다음은 예시에 대한 설명이다.

• 재훈이의 핸드폰에서, 0초의 시간이 소요된 상태에서, 학인봇이 나타났기 때문에 재훈이는 5초간 기다린 후에 다음 구간으로 이동해야한다.
• 첫 번째 스위치에서, 6초의 시간이 소요된 상태에서, 학인봇의 쉬는 시간이기 때문에 재훈이는 기다리지 않고 바로 이동할 수 있다.
• 두 번째 라우터에서, 7초의 시간이 소요된 상태에서, 학인봇의 활동이 2초 남았기 때문에 재훈이는 2초 기다린 후에 이동해야 한다.
• 세 번째 서버에서, 10초의 시간이 소요된 상태에서, 학인봇의 활동이 4초 남았기 때문에 재훈이는 4초 기다린 후에 이동해야 한다.

예시에서 재훈이가 과일노리에 접속하는 데에는 최소 15초의 시간이 소요되었다.

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

첫째 줄에 재훈이가 거쳐야하는 구간의 수 N이 주어진다. (1 ≤ N ≤ 50,000)

이후 N개의 줄에 걸쳐 i번째 구간에서의 학인봇의 활동 정보 (a, b)가 주어진다. 이는 학인봇이 a초 간격으로 나타나, b초 동안 활동 후에 사라진다는 뜻이다. (1 ≤ a, b ≤ 1,000)

재훈이가 과일노리에 접속하기 위해 필요한 최소 소요시간을 출력한다.