题目描述

AtCoDeer 是一只鹿，在电视上看到了一份选举结果的快速报告。有两位候选人参加选举：Takahashi 和 Aoki。该报告显示了两位候选人当前获得的选票比例，但没有显示实际的选票数。AtCoDeer 检查了报告 $N$ 次，在第 $i$ 次检查时 $(1≦i≦N)$，比例为 $T_i:A_i$。已知每个候选人在第一次检查报告时至少获得了一张选票。

请找出当他在第 $N$ 次检查报告时，两位候选人可能获得的最少总选票数。可以假设每个候选人获得的选票数不会减少。

约束条件

• $1≦N≦1000$
• $1≦T_i,A_i≦1000 (1≦i≦N)$
• $T_i$ 和 $A_i$ $(1≦i≦N)$ 互质。
• 保证正确答案最多为 $10^{18}$。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $T_1$ $A_1$ $T_2$ $A_2$ $:$ $T_N$ $A_N$

输出

输出 AtCoDeer 在第 $N$ 次检查报告时，Takahashi 和 Aoki 可能获得的最少总选票数。

示例输入1

3
2 3
1 1
3 2

示例输出1

10

当两位候选人获得的选票数变化为 $2,3 → 3,3 → 6,4$ 时，最终的总选票数为 $10$，这是最小可能的数量。

示例输入2

4
1 1
1 1
1 5
1 100

示例输出2

101

可能出现的情况是，在他检查报告的时刻和下次检查报告的时刻之间，两位候选人都没有获得选票。

示例输入3

5
3 10
48 17
31 199
231 23
3 2

示例输出3

6930