Problem:
 Score : 300 points    Problem Statement AtCoDeer the deer is seeing a quick report of election results on TV.
Two candidates are standing for the election: Takahashi and Aoki.
The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes.
AtCoDeer has checked the report N times, and when he checked it for the i -th (1≦i≦N) time, the ratio was T_i:A_i .
It is known that each candidate had at least one vote when he checked the report for the first time.  Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the N -th time.
It can be assumed that the number of votes obtained by each candidate never decreases.      Constraints  1≦N≦1000  1≦T_i,A_i≦1000 (1≦i≦N)  T_i and A_i  (1≦i≦N) are coprime.  It is guaranteed that the correct answer is at most 10^{18} .         Input The input is given from Standard Input in the following format:  N  T_1  A_1  T_2  A_2  :  T_N  A_N       Output Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the N -th time.        Sample Input 1 3
2 3
1 1
3 2      Sample Output 1 10  When the numbers of votes obtained by the two candidates change as 2,3 → 3,3 → 6,4 , the total number of votes at the end is 10 , which is the minimum possible number.       Sample Input 2 4
1 1
1 1
1 5
1 100      Sample Output 2 101  It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.       Sample Input 3 5
3 10
48 17
31 199
231 23
3 2      Sample Output 3 6930

Solution (Python):
N = int(input())

ans = 1
minT, minA = 1, 1
for _ in range(N):
    T, A = map(int, input().split())
    fT, fA = (minT-1)//T+1, (minA-1)//A+1
    f = max(fT, fA)
    minT, minA = T*f, A*f
print(minT+minA)

Solution (Python):
def main():
    N = int(input())
    a = 1
    t = 1
    for _ in range(N):
        T, A = map(int, input().split())
        if t <= T and a <= A:
            t = T
            a = A
        elif t <= T and a > A:
            tmp = a // A
            if a % A != 0:
                tmp += 1
            t = T * tmp
            a = A * tmp
        elif t > T and a <= A:
            tmp = t // T
            if t % T != 0:
                tmp += 1
            t = T * tmp
            a = A * tmp
        else:
            tmp_A = a // A
            if a % A != 0:
                tmp_A += 1
            tmp_T = t // T
            if t % T != 0:
                tmp_T += 1
            tmp = max(tmp_A, tmp_T)
            t = T * tmp
            a = A * tmp
    print(a + t)



if __name__ == "__main__":
    main()

Solution (Python):
from decimal import Decimal
import math

N = int(input())

T, A = map(Decimal, input().split())

for i in range(1, N):
    t, a = map(Decimal, input().split())
    td = math.ceil(T / t)
    ad = math.ceil(A / a)

    if td < ad:
        T = t * ad
        A = a * ad
    else:
        T = t * td
        A = a * td

print(T + A)

Solution (Python):
import math
N = int(input())
t= 1
a= 1

def t_small(t,a,t1,a1):
    gain = -(-t//t1)
    t = gain*t1
    a_tmp=gain*a1
    if a_tmp<a:
        gain_a = -(-a//a_tmp)
        t *= gain_a
        a = a_tmp*gain_a
    else:
        a = a_tmp
    return t,a,t+a

def a_small(t,a,t1,a1):
    gain = -(-a//a1)
    a = gain*a1
    t_tmp=gain*t1
    if t_tmp<t:
        gain_t = -(-t//t_tmp)
        a *= gain_t
        t = t_tmp*gain_t
    else:
        t = t_tmp
    return t,a,t+a

ans = 0
for _ in range(N):
    t1,a1 = map(int,input().split())
    tt1,aa1,sta1 = t_small(t,a,t1,a1)
    tt2,aa2,sta2 = a_small(t,a,t1,a1)
    if sta1<=sta2:
        t=tt1;a=aa1;ans = sta1
    else:
        t=tt2;a=aa2;ans=sta2
print(ans)

Solution (Python):
N = int(input())

t_cunt = a_cunt = 1

for _ in range(N):
    T,A = map(int,input().split())
    if T < t_cunt or A < a_cunt:
        nt = t_cunt//T + 1 if t_cunt%T else t_cunt//T
        na = a_cunt//A + 1 if a_cunt%A else a_cunt//A
        n = max(nt, na)
        t_cunt = n*T
        a_cunt = n*A
    else:
        t_cunt = T
        a_cunt = A
    
print(t_cunt+a_cunt)

Solution (Python):
N = int(input())
T,A = 1,1
for _ in range(N):
    t,a = map(int,input().split())
    k1 = (T+t-1)//t
    k2 = (A+a-1)//a
    k = max(k1,k2)
    T = k*t
    A = k*a
print(T+A)

Solution (Python):
import math
N = int(input())
T,A = 1,1
for _ in range(N):
    t,a = map(int,input().split())
    k1 = T//t
    if T%t>0:
        k1 += 1
    k2 = A//a
    if A%a>0:
        k2 += 1
    k = max(k1,k2)
    T = k*t
    A = k*a
print(T+A)

Solution (Python):
n = int(input())
TA = [list(map(int, input().split())) for _ in range(n)]

A, B = 1, 1
for t, a in TA:
    n = max((A-1)//t+1, (B-1)//a+1)
    A = n*t
    B = n*a

print(A+B)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
T,A = MI()
for _ in range(N-1):
    t,a = MI()
    x = (T+t-1)//t
    y = (A+a-1)//a
    if x >= y:
        T,A = t*x,a*x
    else:
        T,A = t*y,a*y

print(T+A)

Solution (Python):
import sys

input = sys.stdin.readline
N = int(input())

rates = []
for _ in range(N):
    t, a = map(int, input().split())
    rates.append((t, a))

ans = 0
for i in range(N-1):
    t1, a1 = rates[i]
    t2, a2 = rates[i+1]

    rate = max((t1 - 1) // t2, (a1 - 1) // a2) + 1
    rates[i+1] = (t2 * rate, a2 * rate)

print(sum(rates[N-1]))

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N = I()
T,A = MI()
for _ in range(N-1):
    t,a = MI()
    x = (T+t-1)//t
    y = (A+a-1)//a
    if x >= y:
        T,A = t*x,a*x
    else:
        T,A = t*y,a*y

print(T+A)

Solution (Python):
N = int(input())
t = 1
a = 1
for _ in range(N):
    T, A = map(int,input().split())
    k = max((t - 1) // T + 1, (a - 1) // A + 1)
    t = T * k
    a = A * k
print(a + t)

Solution (Python):
import math
N = int(input())
ans = 1
prea = 1; preb = 1
for i in range(N):
  a,b = map(int,input().split())
  MIN = max((prea+a-1)//a,(preb+b-1)//b)
  
  ans = MIN*(a+b)
  prea = a*MIN; preb = b*MIN
  
print(ans)

Solution (Python):
N = int(input())

A, B = 0, 0

for i in range(N):
    x, y = map(int, input().split())
    if i == 0:
        A = x
        B = y
        continue
    tmpa = (A - 1) // x + 1
    tmpb = (B - 1) // y + 1
    tmp = max(1, tmpa, tmpb)
    x *= tmp
    y *= tmp
    A = x
    B = y

print(A + B)

Solution (Python):
n=int(input())
a,b=1,1
from math import ceil
from decimal import Decimal as D
from fractions import Fraction as F

for i in range(n):
    x,y=map(int,input().split())
    base= max(ceil(F(b,y)),ceil(F(a,x)))
    a= base*x ; b=base*y 
    
print(a+b)

Solution (Python):
n=int(input())
a,b=1,1
from math import ceil

for i in range(n):
    x,y=map(int,input().split())
    base= max((b//y if b%y==0 else b//y+1),(a//x if a%x==0 else a//x+1))
    a= base*x ; b=base*y 
    
print(a+b)

Solution (Python):
n=int(input())
from math import gcd
a,b=map(int,input().split())
temp=a+b
for i in range(1,n):
    c,d=map(int,input().split())
    j=c+d
    
    x=max(a-c,0)//c
    if max(a-c,0)%c!=0:
        x+=1
    y=max(b-d,0)//d
    if max(b-d,0)%d!=0:
        y+=1
    z=max(temp-j,0)//j
    if max(temp-j,0)%j!=0:
        z+=1
    l=[x,y,z]
    temp=max(l)*j+j
    a=max(l)*c+c
    b=max(l)*d+d
        
print(temp)

Solution (Python):
N=int(input())
T=[]
A=[]
for i in range(N):
    t,a=map(int,input().split())
    T.append(t)
    A.append(a)

Tnow=T[0]
Anow=A[0]


for i in range(1,N):
    t=T[i]
    a=A[i]
    t1=(Tnow+t-1)//t*t
    a1=t1//t*a
    a2=(Anow+a-1)//a*a
    t2=a2//a*t
    if a1<Anow:
        Tnow=t2
        Anow=a2
    elif t2<Tnow:
        Tnow=t1
        Anow=a1
    elif t1+a1<=t2+a2:
        Tnow=t1
        Anow=a1
    else:
        Tnow=t2
        Anow=a2
print(Tnow+Anow)

Solution (Python):
def Expand_Euclid(a,b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1

    return x0,y0

N=int(input())
p=q=1
for _ in range(N):
    T,A=map(int,input().split())
    d=T*q-A*p

    alpha,beta=Expand_Euclid(A,T)
    beta=-beta

    x=(-d*alpha+(T-1))//T
    y=(-d*beta+(A-1))//A
    K=max(x,y)

    p+=T*K+d*alpha
    q+=A*K+d*beta
print(p+q)

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N = NI()
    TA = [NLI() for _ in range(N)]
    nt, na = 0, 0
    for t, a in TA:
        if t >= nt and a >= na:
            nt = t
            na = a
        elif t >= nt and a < na:
            k = na // a if na % a == 0 else na // a + 1
            nt = k*t
            na = k*a
        elif t < nt and a >= na:
            k = nt // t if nt % t == 0 else nt // t + 1
            nt = k*t
            na = k*a
        else:
            kt = nt // t if nt % t == 0 else nt // t + 1
            ka = na // a if na % a == 0 else na // a + 1
            k = max(kt, ka)
            nt = k * t
            na = k * a
    print(nt+na)



if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
x,y = 1,1
for _ in range(N):
    t,a = map(int,input().split())
    d = max(-(-x//t),-(-y//a))
    x,y = d*t,d*a
print(x+y)

Solution (Python):
N = int(input())
t,a = map(int,input().split())

for _ in range(1,N):
    T,A = map(int,input().split())
    d = max(-(-t//T),-(-a//A))
    t,a = T*d,A*d
    
print(t+a)

Solution (Python):
from math import ceil
N = int(input())
t,a = map(int,input().split())

for _ in range(1,N):
    T,A = map(int,input().split())
    d = max(-(-t//T),-(-a//A))
    t,a = T*d,A*d
    
print(t+a)

Solution (Python):
n=int(input())
x,y=1,1
for _ in range(n):
  t,a=map(int,input().split())
  m=max((x+t-1)//t,(y+a-1)//a)
  x,y=m*t,m*a
print(x+y)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    n = ni()
    t, a = 1, 1

    for _ in range(n):
        ti, ai = ns()

        
        
        
        

        x = t // ti
        x += 1 if t % ti else 0
        y = a//ai
        y += 1 if a % ai else 0

        nxt = max(x, y)

        t, a = ti * nxt, ai * nxt

    print(t + a)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = 1
B = 1
for _ in range(N):
    a, b = map(int, input().split())
    if a == b:
        A = max(A, B)
        B = max(A, B)
    else:
        if A%a == 0:
            aa = A//a
        else:
            aa = A//a + 1
        if B%b == 0:
            bb = B//b
        else:
            bb = B//b + 1
        tmp = max(aa, bb)
        A = tmp*a
        B = tmp*b

print(A+B)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    TA = [LI() for _ in range(N)]

    t, a = TA[0]
    for i in range(1, N):
        T, A = TA[i]
        
        if t * A > a * T:
            rate = (t - 1) // T + 1
            t = T * rate
            a = A * rate
        else:
            rate = (a - 1) // A + 1
            t = T * rate
            a = A * rate

    print(t + a)

if __name__ == '__main__':
    resolve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    TA = [LI() for _ in range(N)]

    t, a = TA[0]
    for i in range(1, N):
        T, A = TA[i]
        
        if t * A > a * T:
            t = T * ((t - 1) // T + 1)
            a = A * ((t - 1) // T + 1)
        else:
            t = T * ((a - 1) // A + 1)
            a = A * ((a - 1) // A + 1)

    print(t + a)

if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
t, a = map(int, input().split())
for i in range(n-1):
  ti, ai = map(int,input().split())
  ma=max(t, a)
  if ti==1 and ai ==1:
    t=ma
    a=ma
  else:
    temp=[0]*7
    temp[1] = t%ti
    if temp[1]!=0:
      temp[1] = ti-temp[1]
    temp[2] = t+temp[1]       
    temp[3] = (temp[2]//ti)*ai 
    
    temp[4] = a%ai
    if temp[4] != 0:
      temp[4] = ai-temp[4]
    temp[5] = a+temp[4]
    temp[6] = (temp[5]//ai)*ti
    
    if temp[3]-a<0 and temp[4]+temp[6]-t>=0:
      a=temp[5]
      t=temp[6]
    elif temp[1]+temp[3]-a>=0 and temp[6]-t<0:
      a=temp[3]
      t=temp[2]
    elif temp[1]+temp[3]-a<temp[4]+temp[6]-t:
      a=temp[3]
      t=temp[2]
    else:
      a=temp[5]
      t=temp[6]
  

print(int(a+t))

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
nt, na = map(int, input().split())

for _ in range(N-1):
    t, a = map(int, input().split())
    c = max((nt+t-1)//t, (na+a-1)//a)
    nt = c*t
    na = c*a

print(nt+na)

Solution (Python):
n = int(input())

ab = [list(map(int, input().split())) for _ in range(n)]

x = ab[0][0]
y = ab[0][1]
j = 1
flg = True
for i in range(1,n):
    xx = ab[i][0]
    yy = ab[i][1]
    j = max(x//xx,y//yy)
    while flg:
        if x> j*xx or y > j*yy:
            j +=1
        else:
            x = xx *j
            y = yy *j
            break

print(x+y)

Solution (Python):
n=int(input())
p=[]
for i in range(n):
  p.append(list(map(int,input().split())))

v=[1,1]
for i in p:
  r=max((v[0]-1)//i[0],(v[1]-1)//i[1])+1
  v=[i[0]*r,i[1]*r]

print(v[0]+v[1])

Solution (Python):
import math
n=int(input())
a,b=map(int,input().split())
for _ in range(n-1):
    c,d=map(int,input().split())
    l,r,ans=1,10**18,-1
    while(l<=r):
        m=(l+r)//2
        if(m*c>=a and m*d>=b):
            ans=m
            r=m-1
        else:
            l=m+1
    a=ans*c
    b=ans*d
print(a+b)

Solution (Python):
n = int(input())
ratios = []
for _ in range(n):
    ratios.append(tuple(map(int,input().split())))

a, b = 1, 1

for i in range(n):
    ra, rb = ratios[i]
    m = max(-(-a // ra), -(-b // rb))
    a, b = ra * m, rb * m

print(a + b)

Solution (Python):
N = int(input())
t, a = map(int, input().split())
for i in range(N - 1):
  T, A = map(int, input().split())
  x = max((t - 1) // T + 1, (a - 1) // A + 1)
  t = T * x
  a = A * x
print(t + a)

Solution (Python):
N, *TA = [int(_) for _ in open(0).read().split()]
x, y = TA[:2]
for t, a in zip(TA[2::2], TA[3::2]):
    m = 1 + max((x - 1) // t, (y - 1) // a)
    x = m * t
    y = m * a
print(x + y)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
t,a = map(int, input().split())
import math
for i in range(n-1):
    tt,aa = map(int, input().split())
    if t<=tt and a<=aa:
        t,a = tt,aa
    else:
        t1,a1 = tt*(t//tt + int(t%tt!=0)), aa*(t//tt + int(t%tt!=0))
        t2,a2 = tt*(a//aa + int(a%aa!=0)), aa*(a//aa + int(a%aa!=0))

        if (t1<t2 and t1>=t and a1>=a) or (t2<t or a2<a):
            t,a = t1,a1
        else:
            t,a = t2,a2
ans = t+a
print(ans)

Solution (Python):
n = int(input())

t, a = map(int, input().split())
taka = t
aoki = a
t_a = t / a
for _ in range(n - 1):
    t, a = map(int, input().split())
    if t_a == t / a:
        continue
    elif t_a < t / a:
        tmp = ((aoki - 1) // a + 1)
        aoki = tmp * a
        taka = tmp * t
    else:
        tmp = ((taka - 1) // t + 1)
        aoki = tmp * a
        taka = tmp * t
    t_a = t / a
print(taka + aoki)

Solution (Python):
n=int(input())
ta=[]
for i in range(n):
    ta.append(list(map(int,input().split())))

for i in range(n-1):
    if ta[i+1][0]<ta[i][0] or ta[i+1][1]<ta[i][1]:
        k=max(((ta[i][0]-1)//ta[i+1][0]+1), ((ta[i][1]-1)//ta[i+1][1]+1))
        ta[i+1][0]*=k
        ta[i+1][1]*=k

print(ta[-1][0]+ta[-1][1])

Solution (Python):


from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ta = [list(map(int, input().split())) for _ in range(n)]
    ans = sum(ta[0])
    for i in range(1, n):
        si1 = sum(ta[i - 1])
        si = sum(ta[i])
        cand1 = (ans * ta[i - 1][0] // si1) // ta[i][0] if (ans * ta[i - 1][0] // si1) % ta[i][0] == 0 else (ans * ta[i - 1][0] // si1) // ta[i][0] + 1
        cand2 = (ans * ta[i - 1][1] // si1) // ta[i][1] if (ans * ta[i - 1][1] // si1) % ta[i][1] == 0 else (ans * ta[i - 1][1] // si1) // ta[i][1] + 1
        ans = si * max([cand1, cand2])
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
n=int(input())
t1, a1=map(int, input().split())
t_now=t1
a_now=a1
for _ in range(n-1):
    t, a=map(int, input().split())
    if t==a:
        t_now=max(t_now, a_now)
        a_now=t_now
    else:
        t_tmp=((t_now-1)//t+1)*t
        a_tmp=((a_now-1)//a+1)*a
        t_now=max(t_tmp//t, a_tmp//a)*t
        a_now=max(t_tmp//t, a_tmp//a)*a
print(t_now+a_now)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    TA = in_nl2(N)

    t_score, a_score = 1, 1
    for i in range(N):

        t, a = TA[i]

        if t == a:
            t_score = max(t_score, a_score)
            a_score = t_score
        else:
            t_s = -(-t_score // t) * t
            a_s = (t_s // t) * a
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s
                continue

            a_s = -(-a_score // a) * a
            t_s = (a_s // a) * t
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s

    print(t_score + a_score)


if __name__ == '__main__':
    main()

Solution (Python):
import math
from decimal import Decimal

n = int(input())
cura,curb = 1,1

for i in range(n):
    t,a = map(int,input().split())
    
    xa,xb = Decimal(cura)/Decimal(t),Decimal(curb)/Decimal(a)
    x = math.ceil(max(xa,xb))
    
    cura,curb = t*x,a*x
    
print(cura+curb)

Solution (Python):
def ceil(X, Y):  
    return (X + Y - 1) // Y


n = int(input())
ta = [list(map(int, input().split())) for _ in range(n)]

t, a = 1, 1
for ti, ai in ta:
    tmp = max(ceil(t, ti), ceil(a, ai))
    t, a = ti * tmp, ai * tmp
print(t + a)

Solution (Python):
def main():
    n = int(input())
    x,y = 1,1
    for _ in range(n):
        t,a = map(int,input().split())
        z = -1*min(-x//t,-y//a)
        x = z*t
        y = z*a
        
    print(x+y)

main()

Solution (Python):
import math

N = int(input())

T,A = map(int, input().split())
for _ in range(N-1):
  t,a = map(int, input().split())
  if T % t == 0:
    i = T // t
  else:
    i = T // t + 1
  if A % a == 0:
    j = A // a
  else:
    j = A // a + 1
  k = max(i,j)
  T = k*t
  A = k*a
  
print(T+A)

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n=II()
	x,y=1,1

	for _ in range(n):
		a,b=MI()
		k=max((x-1)//a,(y-1)//b)+1
		
		x,y=k*a,k*b

	print(x+y)



if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n=II()
	x,y=1,1

	for _ in range(n):
		a,b=MI()
		k=max((x-1)//a,(y-1)//b)+1
		
		x,y=k*a,k*b

	print(x+y)



if __name__ == "__main__":
	main()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

import math

N = int(readline())
T,A = map(int,readline().split())

def update(T,A,t,a):
    T1 = (T+t-1)//t*t
    A1 = T1//t*a
    A2 = (A+a-1)//a*a
    T2 = A2//a*t
    return max(T1,T2),max(A1,A2)

for i in range(N-1):
    t,a = map(int,readline().split())
    T,A = update(T,A,t,a)
print(T+A)

Solution (Python):






import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
x,y=MI()
def nex(a,b,c,d):
    u=max(-(-a//c),-(-b//d))
    return [u*c,u*d]

for i in range(n-1):
    a,b=MI()
    x,y=nex(x,y,a,b)
print(x+y)

Solution (Python):
import math
n = int(input())
x = 1
y = 1
for i in range(n):
    t, a = map(int, input().split())
    z = max((x-1)//t+1, (y-1)//a+1)
    x = t*z
    y = a*z
print(x+y)

Solution (Python):



from math import ceil
from decimal import Decimal

N=int(input())
T=[0]*N
A=[0]*N
p=1
q=1
for i in range(N):
    T[i],A[i]=map(int,input().split())
   
    s = ceil(p/T[i])
    t = ceil(q/A[i])
    r = max(s,t)
    p = Decimal(T[i]*r)
    q = Decimal(A[i]*r) 
    
    
print(p+q)

Solution (Python):
n = int(input())
t,a = map(int,input().split())
nowt = t
nowa = a
for i in range(n-1):
    t , a = map(int,input().split())
    kou = max(nowt//t,nowa//a)
    while True:
        if t*kou >= nowt and a*kou >= nowa:
            break
        else:
            kou += 1
    nowt = t*kou
    nowa = a*kou
print(nowt+nowa)

Solution (Python):
n=int(input())
t=a=1
for i in range(n):T,A=map(int,input().split());m=max(-(-t//T),-(-a//A));t=T*m;a=A*m
print(t+a)

Solution (Python):
def main():
    n = int(input())
    a, b = 1, 1
    ceil = lambda x, y: -(-x // y)
    for _ in range(n):
        c, d = list(map(int, input().split()))
        r = max(ceil(a, c), ceil(b, d))
        a = c * r
        b = d * r
    print(a + b)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
na,nt = 1,1
for i in range(n):
    a,t = map(int, input().split())
    ra = (na-1)//a + 1        
    rt = (nt-1)//t + 1
    r = max(ra,rt)        
    na = a*r
    nt = t*r
    


print(na+nt)

Solution (Python):
def ceil(a, b):
	return -(-a//b)

n = int(input())
chokudai, aoki = 0, 0
for i in range(n):
	t, a = map(int,input().split())
	if i == 0:
		chokudai, aoki = t, a
		continue
	bairitsu = max(ceil(chokudai, t), ceil(aoki, a))
	t *= bairitsu
	a *= bairitsu
	
	chokudai, aoki = t, a
print(chokudai + aoki)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*ta = map(int, read().split())


v=w=1
mp = iter(ta)
for t,a in zip(mp,mp):
    x = max((v+t-1)//t,(w+a-1)//a)
    v = t*x
    w = a*x
    
    
print(v+w)

Solution (Python):
n=int(input())
T,A=map(int,input().split())
for i in range(n-1):
    t,a=map(int,input().split())
    num1=-1*(T//-t)
    num2=-1*(A//-a)
    T=t*max(num1,num2)
    A=a*max(num1,num2)
print(T+A)

Solution (Python):
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = max((p + x - 1) // x, (q + y - 1) // y)
        p = x * k
        q = y * k
    return p + q


print(solve())

Solution (Python):
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = max(p // x, q // y, 1)
        while True:
            if x * k >= p and y * k >= q:
                p = x * k
                q = y * k
                break
            k += 1
    return p + q


print(solve())

Solution (Python):
n = int(input())


def check(i):
    return T <= t*i and A <= a*i


T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    L = 1
    R = 10**18
    flag = 0
    while True:
        M = (L+R)//2
        if check(M):
            R = M
        else:
            L = M
        if flag:
            break
        if L == R-1:
            flag = 1
    T = t*R
    A = a*R


print(T+A)

Solution (Python):
n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    x = max(-(-T//t), -(-A//a))
    T = t*x
    A = a*x

print(T+A)

Solution (Python):
n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    total = T+A
    x = -(-total//(a+t))
    x = max(x, -(-T//t))
    x = max(x, -(-A//a))
    T = t*x
    A = a*x

print(T+A)

Solution (Python):
n = int(input())
TA = [tuple(map(int, input().split())) for _ in range(n)]
s, a = 1, 1
for d, f in TA:
    k = max(-(-a//d), -(-s//f))
    s, a = f*k, d*k
print(s+a)

Solution (Python):
n=int(input())
a,b=map(int,input().split())
for i in range(n-1):
  x,y=map(int,input().split())
  if x*b>y*a:
    if b%y!=0:
      b+=y-(b%y)
    r=b//y
    a=x*r
  else:
    if a%x!=0:
      a+=x-(a%x)
    r=a//x
    b=y*r
print(a+b)

Solution (Python):
from math import ceil

N = int(input())
T = []
A = []

for _ in range(N):
    t, a = list(map(int, input().split()))
    T.append(t)
    A.append(a)

t_num = T[0]
a_num = A[0]
for i in range(1, N):
    tn = (t_num + T[i] - 1) // T[i]
    an = (a_num + A[i] - 1) // A[i]
    n = max(tn, an)
    t_num = T[i] * n
    a_num = A[i] * n

print(t_num + a_num)

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=II()
	a=1
	b=1

	for n in range(n):
		x,y=MI()
		if a<=x and b<=y:
			a,b=x,y
		elif a>x and b>y:
			t=max((a-1)//x,(b-1)//y)+1
			a,b=t*x,t*y
		elif a>x:
			t=(a-1)//x+1
			a,b=t*x,t*y
		else:
			t=(b-1)//y+1
			a,b=t*x,t*y

	print(a+b)





















if __name__ == "__main__":
	main()

Solution (Python):
n=int(input())
a,s=map(int,input().split())
for i in range(n-1):
    d,f=map(int,input().split())
    k=max(-(-a//d),-(-s//f))
    a=d*k;s=f*k

print(a+s)

Solution (Python):
N = int(input())
TA = []
for i in range(N):
    TA.append(list(map(int,input().split())))

L = [[0]*2 for i in range(N)]

L[0][0] = TA[0][0]
L[0][1] = TA[0][1]

for i in range(1,N):
    T = TA[i][0]
    A = TA[i][1]
    Tm = L[i-1][0]
    Am = L[i-1][1]

    Tamari = Tm%T
    if Tamari==0:
        Tn = Tm
    else:
        Tn = Tm + (T-Tamari)

    Aamari = Am%A
    if Aamari==0:
        An = Am
    else:
        An = Am + (A-Aamari)

    if T<A:
        L[i][0],L[i][1] = Tn,Tn//T*A
        if L[i][1]<L[i-1][1]:
            L[i][0],L[i][1] = An//A*T,An
    elif T>A:
        L[i][0],L[i][1] = An//A*T,An
        if L[i][0]<L[i-1][0]:
            L[i][0],L[i][1] = Tn,Tn//T*A
    else:
        L[i][0],L[i][1] = max(L[i-1][0],L[i-1][1]),max(L[i-1][0],L[i-1][1])

print(L[-1][0]+L[-1][1])

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
T, A = map(int,readline().split())

for i in range(N - 1):
  t,a = map(int,readline().split())
  n = max((T + t - 1)//t,(A + a - 1)//a)
  T,A = n*t,n*a
  
print(T + A)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
T, A = map(int,readline().split())

for i in range(N - 1):
  t,a = map(int,readline().split())
  
  
  
  
  minT = ((T + t - 1) // t) * t
  minA = minT * a // t
  if minA >= A:
    T,A = minT,minA
    continue
  minA = ((A + a - 1) // a) * a
  minT = minA * t // a
  T,A = minT,minA
  
print(T + A)

Solution (Python):


from fractions import Fraction
import math

N = int(input())
TA = [tuple(map(int, input().split())) for _ in range(N)]

"""
Ti : Ai = t : a の時、整数xを使って、i回目のそれぞれの得票数を、t * x, a * x と表せる。
なので、一回前のそれぞれの得票数がわかっている場合、xの範囲がわかるので、xが最小になるように更新していく
"""


T = 0
A = 0
for i,(t,a) in enumerate(TA):
    if i == 0:
        T = t
        A = a
    else:
        x = math.ceil(max(Fraction(T, t), Fraction(A, a)))
        T = t * x
        A = a * x


print(T+A)

Solution (Python):
n = int(input())
c = []
for i in range(n):
  t,a = map(int,input().split())
  c.append((t,a))
  
al = c[0][0]
ar = c[0][1]
for i in range(n):
  if i == 0:
    continue
  b = max((al-1)//c[i][0]+1,(ar-1)//c[i][1]+1)
  al = c[i][0]*b
  ar = c[i][1]*b
  
print(al+ar)

Solution (Python):
import math
n = int(input())
t,a = map(int,input().split())
mi = [t,a]
for i in range(1,n):
    t,a = map(int,input().split())
    ts = max((mi[0]-1)//t,(mi[1]-1)//a)+1
    mi = [t*ts,a*ts]

print(mi[0]+mi[1])