配点 : $300$ 点

問題文

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

制約

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

入力

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

$N$

$T_1$ $A_1$

$T_2$ $A_2$

$:$

$T_N$ $A_N$

出力

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

3
2 3
1 1
3 2

10

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

4
1 1
1 1
1 5
1 100

101

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

5
3 10
48 17
31 199
231 23
3 2

6930