分数: 300 点
问题陈述
AtCoDeer,鹿正在电视上看到选举结果的快速报道。 两名候选人参加选举:高桥和青木。 报告显示了两位候选人当前获得的票数比例,但并未显示实际得票数。 AtCoDeer已查看报告 N 次,当他检查时 i-th (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 检查报告时 Takahashi 和 Aoki 获得的最小可能总票数 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