← 返回题目列表

Codeforces · 879/A

A. 博里亚的诊断

中文机器翻译题面 查看原题

看来博利亚病得很重。他要去拜访n位医生以找出确切的诊断。每个医生都需要有关之前所有就诊的信息,因此 Borya 必须按照规定的顺序去看医生(即 Borya 应该首先去看医生 1,然后是医生 2,然后是医生 3,依此类推)。博利亚将从上一位医生那里得到有关他健康状况的信息。

医生的工作时间表很奇怪。我的医生第六天上班,每天都工作。所以,他在 si、si + di、si + 2di 日工作,......

医生的预约需要相当长的时间,所以博利亚每天最多只能看一位医生。他最少需要多少时间去看所有医生?

输入

第一行包含一个整数 n — 医生数量 (1 ≤ n ≤ 1000)。

接下来的 n 行包含两个数字 si 和 di (1 ≤ si, di ≤ 1000)。

输出

输出一个整数——Borya 可以去看最后一位医生的最短天数。

示例

输入 #1

3
2 2
1 2
2 2

输出 #1

4

输入 #2

2
10 1
6 5

输出 #2

11

注意

在第一个样本案例中,Borya 可以在第 2、3 和 4 天拜访所有医生。

在第二个示例案例中,Borya 可以在第 10 天和第 11 天拜访所有医生。