← 返回题目列表

AtCoder · arc062_a

C. AtCoDeer 和选举报告

中文机器翻译题面 查看原题

分数: 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