题目描述

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは $N$ 回画面を見て、 $i(1≦i≦N)$ 回目に見たときに表示されている比は $T_i:A_i$ でした。ここで、AtCoDeerくんが選挙速報の画面を$1$回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 $N$ 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$N$ 回目に画面を見たときの投票数として考えられる最小値を出力せよ。

题目大意

给定 $n$ 和 $n$ 对正整数 $T_i,A_i$，已知正整数数列 $t_i,a_i$ 满足以下条件：

• $t_i\le t_{i+1}$，$a_i\le a_{i+1}$
• $t_i/a_i=T_i/A_i$

求 $t_n+a_n$ 的最小值，保证答案不超过 $10^{18}$。

3
2 3
1 1
3 2

10

4
1 1
1 1
1 5
1 100

101

5
3 10
48 17
31 199
231 23
3 2

6930

提示

制約

• $1≦N≦1000$
• $1≦T_i,A_i≦1000\ (1≦i≦N)$
• $T_i$ と $A_i$ は互いに素 $(1≦i≦N)$
• 答えが $10^{18}$ 以下になることは保証されている

Sample Explanation 1

二人の得票数が $2,3$ -> $3,3$ -> $6,4$ と動くと投票数は $10$ になって、これが最小値です。

Sample Explanation 2

一度画面を見てからもう一度画面を見るまでに一票も入ってないことがありえます。