問題文

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは $N$ 回画面を見て、 $i(1≦i≦N)$ 回目に見たときに表示されている比は $T_i:A_i$ でした。ここで、AtCoDeerくんが選挙速報の画面を$1$回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 $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$

出力

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

入力例 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