看来博利亚病得很重。他要去拜访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 天拜访所有医生。