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())
A, B = 0, 0
for i in range(n):
    x, y = map(int,input().split())
    dx, dy = 1, 1
    if A > x:
        dx = A // x
        if A % x != 0:
            dx += 1
    
    if B > y:
        dy = B // y
        if B % y != 0:
            dy += 1
 
    a = max(dx, dy)
    A, B = a * x, a * y
print(A + B)

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N = i_input()
    t0,a0 = 1,1

    for i in range(N):
        t1,a1 = i_map()
        f0 = t0//t1
        if t0%t1 != 0:
            f0 += 1
        f1 = a0 // a1
        if a0%a1 != 0:
            f1 += 1
        f = max(f0, f1)
        t0, a0 = t1*f, a1*f
    print(t0+a0)

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
A, B = 0, 0
for i in range(n):
    x, y = map(int,input().split())
    dx, dy = 1, 1
    if A > x:
        dx = A // x
        if A % x != 0:
            dx += 1
    
    if B > y:
        dy = B // y
        if B % y != 0:
            dy += 1

    a = max(dx, dy)
    A, B = a * x, a * y
print(A + B)

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

t0, a0 = 1, 1

for i in range(n):
    t1, a1 = map(int, input().split())
    f0 = t0 // t1
    if t0 % t1 != 0:f0 += 1
    f1 = a0 // a1
    if a0 % a1 != 0:f1 += 1
    f = max(f0, f1)
    t0, a0 = t1*f, a1*f

print(t0 + a0)

Solution (Python):
n=int(input())
ans_t=1
ans_a=1
for i in range(n):
    t,a=map(int,input().split())
    if t==1:
        k1=ans_t
    else:
    	k1=(ans_t-1)//t+1
    if a==1:
        k2=ans_a
    else:
    	k2=(ans_a-1)//a+1
    k=max(k1,k2)
    ans_t=k*t
    ans_a=k*a
print(ans_t+ans_a)

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

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

Solution (Python):
from math import gcd

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        pre_a, pre_b = a, b
    if pre_a * b < pre_b * a:
        mul = (pre_b + b - 1) // b
        pre_b = mul * b
        pre_a = pre_b * a // b
    else:
        mul = (pre_a + a - 1) // a
        pre_a = mul * a
        pre_b = pre_a * b // a
    
print(pre_a + pre_b)

Solution (Python):
n = int(input())
A,B = 0,0
for i in range(n):
    x,y = map(int,input().split())
    t,a = 1,1
    if A > x:
        t = A // x
        if A % x != 0:
            t += 1
    if B > y:
        a = B // y
        if B % y != 0:
            a += 1
    m = max(t,a)
    A = x*m
    B = y*m
print(A+B)

Solution (Python):
class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1 for i in range(self.n + 1)]
        self.finv = [1 for i in range(self.n + 1)]
        for i in range(2, self.n+1):
            self.fac[i] = (self.fac[i - 1] * i) % self.mod
            self.finv[i] = (self.finv[i-1] * pow(i, -1, self.mod)) % self.mod

    def comb(self, n, m):
        return self.fac[n] * (self.finv[n-m] * self.finv[m] % self.mod) % self.mod
def iparse():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    ml = 1
    last = [0,0]
    for i in range(n):
        x = iparse()
        
        l = (last[0] + x[0] - 1) // x[0]
        r = (last[1] + x[1] - 1) // x[1]
        m = max(l, r)
        if m == 0:
            m = 1
        x[0] *= m
        x[1] *= m
        
        last = x
    print(sum(last))

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

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

Solution (Python):
from math import ceil
from decimal import Decimal, getcontext
getcontext().prec = 100
N = int(input())
TA = [tuple(map(int, input().split())) for _ in range(N)]

T = 1
A = 1
for i in range(N):
    x, y = TA[i]
    n = max(ceil(Decimal(T)/Decimal(x)), ceil(Decimal(A)/Decimal(y)))
    T = n*x
    A = n*y
print(T+A)

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

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        
        
        
        
        t = sum_t
        a = sum_a
        continue

print(t + a)

Solution (Python):
import math

n=int(input())
ans=list(map(int,input().split()))
if n==1:
  print(sum(ans))
  
else:
  ans1=[]
  ans1.append(ans)
  for i in range(n-1):
    x,y=map(int,input().split())
    p,q=ans1[-1][0],ans1[-1][1]
    if p%x==0:
      p1=p//x
    else:
      p1=p//x+1
    if q%y==0:
      q1=q//y
    else:
      q1=q//y+1
    pq=max(p1,q1)
    r=[x*pq,y*pq]
    ans1.append(r)
    
  print(sum(ans1[-1]))

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

T = 1
A = 1
for i in range(N):
    bai = max(-(-T//ls[i][0]),-(-A//ls[i][1]))
    T = bai * ls[i][0]
    A = bai * ls[i][1]
print(T+A)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

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

    print(t + a)




if __name__ == "__main__":
    main()

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

x, y = 1, 1
for t, a in query:
    if t >= x and a >= y:
        x = t
        y = a
    else:
        if t < x and a < y:
            x = t * max((x + t - 1) // t, (y + a - 1) // a)
            y = a * max((x + t - 1) // t, (y + a - 1) // a)
        elif t < x:
            x = t * ((x + t - 1) // t)
            y = a * ((x + t - 1) // t)
        else:
            x = t * ((y + a - 1) // a)
            y = a * ((y + a - 1) // a)
print(x + y)

Solution (Python):
N = int(input())
Ratio = [tuple(map(int, input().split())) for _ in range(N)]
from math import ceil
Vote = (1, 1)
for t,a in Ratio:
    p = max((t+Vote[0]-1)//t, (a+Vote[1]-1)//a)
    Vote = (p*t, p*a)
print(sum(Vote))

Solution (Python):
import copy
n = int(input())
vote_ls = [[0,0] for _ in range(n)]
for i in range(n):
    a,b = map(int,input().split())
    vote_ls[i] = [a,b]

def check(previous,now):
    ok = True
    for j in [0,1]:
        if previous[j] > now[j]:
            ok = False
    return ok

previous = vote_ls[0]
for i in range(1,n):
    now = copy.copy(vote_ls[i])
    if check(previous,now):
        previous = now
        continue

    time_a = -(-previous[0]//now[0])
    time = float('inf')
    if now[1] * time_a >= previous[1]:
        time = min(time,time_a)
    time_b = -(-previous[1]//now[1])
    if now[0] * time_b >= previous[0]:
        time = min(time,time_b)
    now[0]*=time
    now[1]*=time
    previous = now

print(sum(previous))

Solution (Python):




import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
2 3
1 1
3 2"""
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 1
1 1
1 5
1 100"""
        output = """101"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
3 10
48 17
31 199
231 23
3 2"""
        output = """6930"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    R = [list(map(int, input().split())) for _ in range(N)]

    t = R[0][0]
    a = R[0][1]
    for i in range(1, N):
        n = max((t+R[i][0]-1)//R[i][0], (a+R[i][1]-1)//R[i][1])
        t = n*R[i][0]
        a = n*R[i][1]

    print(t+a)


if __name__ == "__main__":
    
    resolve()

Solution (Python):
a,b = 1,1
for i in range(int(raw_input())):
	n,d = map(int, raw_input().split())
	q = max((a+n-1)/n, (b+d-1)/d)
	a,b= n*q, d*q
print a+b

Solution (Python):
for i in range(int(raw_input())):
	n,d = map(int, raw_input().split())
	if i == 0:
		a,b = n,d
	else:
		q = max((a+n-1)/n, (b+d-1)/d)
		a = n*q
		b = d*q



print a+b

Solution (Python):
N = int(input())
TNow,ANow = (int(T) for T in input().split())
for TN in range(1,N):
    TNext,ANext = (int(T) for T in input().split())
    Magn = max(TNow//TNext+(TNow%TNext!=0),ANow//ANext+(ANow%ANext!=0))
    TNow,ANow = TNext*Magn,ANext*Magn
print(TNow+ANow)

Solution (Python):
n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    if x <= t and y <= a:
        x = t
        y = a
    else:
        if x % t == 0:
            i_x = x // t
        else:
            i_x = x // t + 1

        if y % a == 0:
            i_y = y // a
        else:
            i_y = y // a + 1
        bigger = max(i_x, i_y)
        x = bigger*t
        y = bigger*a
print(x+y)

Solution (Python):
n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    if x <= t and y <= a:
        x = t
        y = a
    elif x <= t and y > a:
        if y % a == 0:
            i = y // a
        else:
            i = y // a + 1
        y = i*a
        x = i*t
    elif x > t and y <= a:
        if x % t == 0:
            i = x // t
        else:
            i = x // t + 1
        x = i*t
        y = i*a
    elif x > t and y > a:
        if x % t == 0:
            i_x = x // t
        else:
            i_x = x // t + 1

        if y % a == 0:
            i_y = y // a
        else:
            i_y = y // a + 1
        bigger = max(i_x, i_y)
        x = bigger*t
        y = bigger*a
print(x+y)

Solution (Python):
n = int(input())
vote_t = 1
vote_a = 1
    
for _ in range(n):
    t,a = list(map(int, input().split()))
    n = max((vote_t + t - 1) // t, (vote_a + a -1) // a)
    vote_t = n * t
    vote_a = n * a

print(vote_t + vote_a)

Solution (Python):
n=int(input())
a,b=1,1

for i in range(n):
  x,y=map(int,input().split())
  s=-(-a//x)
  t=-(-b//y)
  a,b=max(s,t)*x,max(s,t)*y

print(a+b)

Solution (Python):
def main():
    N = int(input())
    T1, A1 = map(int, input().split())
    for _ in range(N-1):
        T2, A2 = map(int, input().split())
        n = max(-(-T1//T2),-(-A1//A2))
        T1,A1 = T2*n,A2*n
    print(T1 + A1)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
p,q=1,1

for _ in range(n):
    t,a=map(int,input().split())
    
    
    
    n=max((p+t-1)//t,(q+a-1)//a)
    p,q=n*t,n*a
    

print(p+q)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
data = []
X = []
for i in range(N):
    T, A = map(int, readline().split())
    data.append((T,A))

T_pre,A_pre = data[0] 
for i in range(1,N):
    T,A = data[i]
    n = max(-(-T_pre//T),-(-A_pre//A))
    T_pre = n*T
    A_pre = n*A
print(T_pre+A_pre)

Solution (Python):
n = int(input())
t_v = a_v = 1
for _ in range(n):
    t, a = [int(x) for x in input().split()]
    r = max((t_v + t - 1) // t, (a_v + a - 1) // a)
    t_v, a_v = r * t, r * a
print(t_v + a_v)

Solution (Python):
n = int(input())
t_all, a_all = 0, 0
for i in range(n):
    t, a = map(int, input().split())
    if i == 0:
        t_all = t
        a_all = a
    else:
        if t >= t_all and a >= a_all:
            t_all, a_all = t, a
        else:
            diff1, diff2 = 0, 0
            diff1 = t_all // t if t_all % t == 0 else t_all // t + 1
            diff2 = a_all // a if a_all % a == 0 else a_all // a + 1
            max_diff = max(diff1, diff2)
            t_all = t * max_diff
            a_all = a * max_diff
print(t_all + a_all)

Solution (Python):
import math
from fractions import Fraction
from decimal import *


n = int(input())
x, y = map(int, input().split())
t, a = x, y

for _ in range(n - 1):
    tt, aa = map(int, input().split())

    
    '''
    if (t >= a):
        c = math.ceil(tt / t)

    else:
        c = math.ceil(aa / a)
    '''
    
    
    c = max(math.ceil(Fraction(t, tt)), math.ceil(Fraction(a, aa)))
    c = max(1, c)

    t = tt * c
    a = aa * c


ans = t + a
print(ans)

Solution (Python):
n = int(input())
t_i,a_i = map(int,input().split())
t = []
a = []
t.append(t_i)
a.append(a_i)
for i in range(1,n):
    t_i,a_i = map(int,input().split())
    t.append(t_i)
    a.append(a_i)
    if t[i-1]>t[i] or a[i-1]>a[i]:
        t_max = t[i-1]//t[i]
        if t[i-1]%t[i]!=0:
            t_max += 1
        a_max = a[i-1]//a[i]
        if a[i-1]%a[i]!=0:
            a_max += 1
        bai = max(t_max,a_max)
        t[i] *= bai
        a[i] *= bai
print(t[-1]+a[-1])

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

Solution (Python):
N = int(input())
T = 1
A = 1
for i in range(N):
    ti, ai = map(int, input().split())
    if T <= A:
        if T % ti == 0:
            TT = T
        else:
            TT = ti - (T % ti) + T
        if A <= (TT // ti) * ai:
            T = TT
            A = (TT // ti) * ai
        else:
            if A % ai != 0:
                A = ai - (A % ai) + A
            T = (A // ai) * ti
    else:
        if A % ai == 0:
            AA = A
        else:
            AA = ai - (A % ai) + A
        if T <= (AA // ai) * ti:
            A = AA
            T = (AA // ai) * ti
        else:
            if T % ti != 0:
                T = ti - (T % ti) + T
            A = (T // ti) * ai
        
print(T+A)

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

n = int(input())

def adjust(x, y):
    if x % y == 0:
        return x // y
    else:
        return x//y + 1

ta, ao = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    mul = max([adjust(ta, t), adjust(ao, a)])
    ta = mul * t
    ao = mul * a

print(ta + ao)

Solution (Python):
def ceil(x, y):
    
    return (x + y - 1) // y


def main():
    n = int(input())
    takahashi = 1
    aoki = 1
    for _ in range(n):
        t, a = map(int, input().split())
        diff = max(ceil(takahashi, t), ceil(aoki, a))
        takahashi = t * diff
        aoki = a * diff
    print(takahashi + aoki)


if __name__ == '__main__':
    main()

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

Solution (Python):
n = int(input())
T, A = map(int, input().split())

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

Solution (Python):
T = 1
A = 1

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

print(T+A)

Solution (Python):
def waru(k,l):
  if k%l==0:
    return k//l
  else:
    return (k//l)+1
A=0
B=0
N=int(input())
for i in range(N):
  a,b=map(int,input().split())
  if a>=A and b>=B:
    A,B=a,b
  elif a>=A and b<B:
    A,B=a*waru(B,b),b*waru(B,b)
  elif a<A and b>=B:
    A,B=a*waru(A,a),b*waru(A,a)
  else:
    c=max(waru(A,a),waru(B,b))
    A,B=a*c,b*c
print(A+B)

Solution (Python):
from sys  import stdin,stdout

import bisect

import math

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)
                
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r

    
def solve():
    n=inp()
    a,b=1,1
    for _ in range(n):
        x,y=mp()
        d=max((x+a-1)//x,(y+b-1)//y)
        a=d*x
        b=d*y
    pr(a+b)
for _ in range(1):
    solve()

Solution (Python):
N=int(input())
A,B=1,1
for i in range(N):
   tmpl=list(map(int,input().split()))
   tmp=max(-1*(-1*A//tmpl[0]),-1*(-1*B//tmpl[1]))
   A,B=tmpl[0]*tmp,tmpl[1]*tmp
print(A+B)

Solution (Python):
import math

n=int(input())
t,a=map(int,input().split())
vt=t
va=a
for i in range(1,n):
    t, a = map(int, input().split())
    if vt<=t and va<=a:
        vt=t
        va=a
    elif vt>t and va<=a:
        x=-(-vt//t)
        vt,va=x*t,x*a
    elif vt<=t and va>a:
        x=-(-va//a)
        vt,va=x*t,x*a
    else:
        x1 = -(-vt // t)
        x2 = -(-va // a)
        if x1*t+x1*a >=x2*t+x2*a:
            vt, va = x1 * t, x1 * a
        else:
            vt, va = x2 * t, x2 * a

print(va+vt)

Solution (Python):
N=int(input())
x,y=0,0
for i in range(N):
  p=0
  T,A=map(int,input().split())
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print(x+y)

Solution (Python):
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
N=int(input())
x,y=0,0
for i in range(N):
  p=0
  T,A=map(int,input().split())
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print(x+y)

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

t1, a1 = map(int,input().split())

for i in range(n-1):
    t,a = map(int,input().split())
    if t1 * a == t * a1:
        pass
    elif t1 * a < t * a1:
        a1 = -(-a1 // a) * a
        t1 = a1 // a * t
    else:
        t1 = -(-t1 // t) * t
        a1 = t1 // t * a

print(a1+t1)

Solution (Python):
N = int(input())
Q = [tuple(map(int, input().split())) for _ in range(N)]
vote = Q[0]  

for p, q in Q[1:]:
    if p == q:
        g = max(vote)
        vote = (g, g)
    
    p_v0 = ((vote[0] + p - 1) // p) * p
    p_v1 = q * p_v0 // p
    
    q_v1 = ((vote[1] + q - 1) // q) * q
    q_v0 = p * q_v1 // q
    
    if p_v1 < vote[1]:
        vote = (q_v0, q_v1)
    elif q_v0 < vote[0]:
        vote = (p_v0, p_v1)
    else:
        
        if p_v0 + p_v1 <= q_v0 + q_v1:
            vote = (p_v0, p_v1)
        else:
            vote = (q_v0, q_v1)

ans = sum(vote)
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *TA = map(int, read().split())

    x, y = 1, 1

    for t, a in zip(*[iter(TA)] * 2):
        m1 = (x + t - 1) // t
        m2 = (y + a - 1) // a
        m = max(m1, m2)
        x, y = t * m, a * m

    print(x + y)
    return


if __name__ == '__main__':
    main()

Solution (Python):
T = 1
A = 1

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

print(T+A)

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

N = I()
x,y = LI()  
for i in range(1,N):
    T,A = LI()
    a = max((x+T-1)//T,(y+A-1)//A)
    x,y = T*a,A*a

print(x+y)

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

    now_t, now_a = 1,1
    for _ in range(N):
        t, a = map(int,input().split())
        n = max(-(-now_t//t), -(-now_a//a))
        now_t = t * n
        now_a = a * n
    
    print(now_t + now_a)
    
if __name__ == '__main__':
    solve()

Solution (Python):
from math import ceil
def solve():
    N = int(input())
    T = []
    A = []
    for _ in range(N):
        t, a = map(int,input().split())
        T.append(t)
        A.append(a)
    
    now_t = T[0]
    now_a = A[0]

    for i in range(1,N):
        mul = f(now_t,now_a,T[i],A[i])
        now_t = T[i] * mul
        now_a = A[i] * mul
    
    print(now_t + now_a)

def f(now_t, now_a, t, a):
    left = 0
    right = 10 ** 18
    while right - left > 1:
        mid = (right + left) // 2
        if now_t > t * mid or now_a > a * mid:
            left = mid
        else:
            right = mid
    
    return right

if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
anst,ansa=map(int,input().split())
for _ in range(1,n):
    t,a=map(int,input().split())
    if anst>t or ansa>a:
        mul=max(-(-anst//t),-(-ansa//a))
        anst=mul*t
        ansa=mul*a
    else:
        anst=t
        ansa=a
print(anst+ansa)

Solution (Python):
def nextpt(ratio1, ratio2, pt):
  if ratio1[0]*ratio2[1]-ratio1[1]*ratio2[0]>0:
    pt[0]=pt[0]+((-1)*pt[0])%ratio2[0]
    pt[1]=pt[0]*ratio2[1]//ratio2[0]
  else:
    pt[1]=pt[1]+((-1)*pt[1])%ratio2[1]
    pt[0]=pt[1]*ratio2[0]//ratio2[1]
  return pt

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

pt=ratios[0]
for i in range(n-1):
  pt=nextpt(ratios[i], ratios[i+1], pt)

print(sum(pt))

Solution (Python):
n = int(input())
pt, pa = 0, 0
for _ in range(n):
    t, a = tuple(map(int, input().split()))
    l = 0
    r = 10**18+1
    while (r-l) > 1:
        mid = (l+r)//2
        if (t*mid >= pt and a*mid >= pa):
            r = mid
        else:
            l = mid
    pt, pa = t*r, a*r

print(pt+pa)

Solution (Python):
from math import gcd
from math import ceil
n = int(input())
T = [0] * n
A = [0] * n
for i in range(n):
    T[i], A[i] = map(int, input().split())

t, a = 1, 1
for i in range(n):
    t_rate, a_rate = T[i], A[i]
    
    t_mul, a_mul = -(-t // t_rate), -(-a // a_rate)
    
    mul_num = max(t_mul, a_mul)
    t, a = mul_num * t_rate, mul_num * a_rate

print(t + a)

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

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

for _ in range(N - 1):
    nt, na = map(int, input().split(' '))
    if nt >= t and na >= a:
        t = nt
        a = na
    else:
        tr = (t + nt - 1) // nt
        ar = (a + na - 1) // na
        r = max(tr, ar)
        t = r * nt
        a = r * na

print(t + a)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
TA = [LIST() for _ in range(N)]

T = TA[0][0]
A = TA[0][1]

for t, a in TA[1:]:
	p = max(-(-T//t), -(-A//a))
	T = t*p
	A = a*p
	
print(T+A)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
TA = [LIST() for _ in range(N)]

T = TA[0][0]
A = TA[0][1]

for t, a in TA[1:]:
	p = max((T+t-1)//t, (A+a-1)//a)
	T = t*p
	A = a*p
	
print(T+A)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = 1
vote_A = 1
for x, y in TA:
	n = max((vote_T+x-1)//x, (vote_A+y-1)//y)
	vote_T = x * n
	vote_A = y * n
print(vote_A + vote_T)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = 1
vote_A = 1
for x, y in TA:
	n = max(-(-vote_T // x), -(-vote_A // y))
	vote_T = x * n
	vote_A = y * n
print(vote_A + vote_T)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
TA = [LIST() for _ in range(N)]

T = TA[0][0]
A = TA[0][1]

for t, a in TA[1:]:
	p = max(T//t + (T%t!=0), A//a + (A%a!=0))
	T = t*p
	A = a*p
	
print(T+A)

Solution (Python):
n = int(input())
a,b = map(int,input().split())

for i in range(n-1):
    c,d = map(int,input().split())
    x = -min((-a)//c,(-b)//d)
    a,b = c*x,d*x
print(a + b)