题目描述

シカ的 AtCoDeer 君正在观看选举快报。选举中有两位候选人，高桥君和青木君。快报上显示的是两人当前得票数的比例，但并未显示具体的得票数。AtCoDeer 君总共看了 $N$ 次屏幕，第 $i$ 次（$1 \leq i \leq N$）看到的比例是 $T_i:A_i$。已知在第一次看快报时，两位候选人至少各有一票。请你求出在第 $N$ 次看快报时，两人得票数之和可能的最小值。注意，得票数在过程中不会减少。

输入格式

输入以如下格式从标准输入读入。

$N$
$T_1$ $A_1$
$T_2$ $A_2$
$\vdots$
$T_N$ $A_N$

输出格式

请输出第 $N$ 次看快报时，两人得票数之和可能的最小值。

样例 1

输入

3
2 3
1 1
3 2

输出

10

样例 2

输入

4
1 1
1 1
1 5
1 100

输出

101

样例 3

输入

5
3 10
48 17
31 199
231 23
3 2

输出

6930

说明/提示

限制条件

• $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}$

样例解释 1

两人的得票数变化为 $2,3$ → $3,3$ → $6,4$，此时总票数为 $10$，这是最小值。

样例解释 2

在两次看屏幕之间，可能没有任何一票被投出。

由 ChatGPT 4.1 翻译