TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8079
  • 题目
  • P8079选举
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    竞赛班上正在进行AK之王的选举, AK_NOIP和AK_IOI两位同学都AK了,但AK之王只有一位,所以我们决定进行一场投票选举。由于竞赛班上的同学智商普遍偏高,所以不用公布具体的票数,而是只在特定的时候公布候选人的得票比例。老师一共会公布$N$次比例。其中第$i$次的比例为$T_i : A_i$,且$T_i$与$A_i$是互质的。已知每个候选人至少有一票,并且每个人的得票数从不减少。请你找出两位候选人最后获得的最小可能总票数,保证答案在$10^{18}$以内。

    输入格式

    输入的第一行包括一个正整数$N(1 \leq N \leq 1000)$。

    接下来的$N$行每行两个整数$T_i,A_i(1 \leq T_i,A_i \leq 10000(1 \leq i \leq N))$,表示$N$次公布的候选人的得票比例。

    输出格式

    打印AK_IOI和AK_NOIP两位候选人获得的最低投票总数

    样例输入 1

    3
    2 3
    1 1
    3 2

    样例输出 1

    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