页面无法加载？点击这里可能会修复。
Placeholder

#8079

해킹시간 1s 512MB

问题

해커 재훈이는 N개의 구간을 거쳐야 접근이 가능한 애플 서버를 해킹하려고 한다.

각 i번 구간에는 보안로봇이 A_i초 간격으로 나타나, B_i초 동안 침입자를 감시하고 사라진다.

재훈이는 보안로봇들의 감시를 피해 경로 중간의 네트워크 장비에 숨으면서 이동을 해야한다.

각 구간을 통과하는 데에는 1초의 시간이 소요된다. 다음은 예시에 대한 설명이다.

  • 재훈이의 핸드폰에서, 0초의 시간이 소요된 상태에서, 보안로봇이 나타났기 때문에 재훈이는 5초간 기다린 후에 다음 구간으로 이동해야한다.

  • 첫 번째 스위치에서, 6초의 시간이 소요된 상태에서, 보안로봇의 쉬는 시간이기 때문에 재훈이는 기다리지 않고 바로 이동할 수 있다.

  • 두 번째 라우터에서, 7초의 시간이 소요된 상태에서, 보안로봇의 활동이 2초 남았기 때문에 재훈이는 2초 기다린 후에 이동해야 한다.

  • 세 번째 서버에서, 10초의 시간이 소요된 상태에서, 보안로봇의 활동이 4초 남았기 때문에 재훈이는 4초 기다린 후에 이동해야 한다.

예시에서 재훈이가 목적지에 접속하는 데에는 최소 15초의 시간이 소요되었다.

재훈이의 최소접속시간을 계산하는 프로그램을 작성하시오.


输入

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

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


输出

첫 줄에 재훈이의 최소접속시간을 출력한다.


示例 #1

4
3 5
4 1
3 3
6 4
15

示例 #2

3
10 1
10 2
10 3
4

来源

2017 선린 봄맞이 교내대회 G번
需要登录才能编写代码。