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):
import sys
import math
n = int(input())
T,A = 1,1
for i in range(n):
    t,a = map(int,input().split(" "))
    coef = max((T+t-1)//t,(A+a-1)//a)
    T,A = coef * t, coef * a 
print(T+A)

Solution (Python):
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    s, b = 0, 0

    for loop in range(N):
        t, a = map(int, sys.stdin.readline().split())

        if loop == 0:
            s, b = t, a
        else:
            k = max((s + t - 1)//t, (b + a - 1)//a)
            s, b = k*t, k*a

    ans = s + b
    print(ans)



if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
    
t_num , a_num = 1, 1
for t, a in [map(int, input().split()) for _ in range(n)]:
    pre_t_num, pre_a_num = t_num, a_num
    t_num, a_num = t, a
    if t_num < pre_t_num or a_num < pre_a_num:
        t_k = (pre_t_num + t - 1) // t
        a_k = (pre_a_num + a - 1) // a
        m = max(t_k, a_k)
        t_num, a_num = t * m, a * m

ans = t_num + a_num
print()
print(ans)

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

t_num , a_num = 1, 1

for t, a in [map(int, input().split()) for _ in range(n)]:
    pre_t_num, pre_a_num = t_num, a_num
    t_num, a_num = t, a
    if t_num < pre_t_num or a_num < pre_a_num:
        
        t_k = (pre_t_num + t - 1) // t
        a_k = (pre_a_num + a - 1) // a
        m = max(t_k, a_k)
        t_num, a_num = t * m, a * m

ans = t_num + a_num
print()
print(ans)

Solution (Python):
N = int(input())
T = []
A = []
Nb = 0
for i in range(N):
    a, b = map(int,input().split())
    T.append(a)
    A.append(b)
Tn = 1
An = 1
for i in range(N):
        tmp = max((Tn+T[i]-1) // T[i], (An+A[i]-1) // A[i])
        Tn = T[i] * tmp
        An = A[i] * tmp
print(Tn + An)

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

Solution (Python):
import math
n=int(input())
t,a=1,1
for i in range(n):
    ti,ai=map(int,input().split())
    m=max(math.ceil(t/ti), math.ceil(a/ai))
    while t > ti*m or a > ai*m:
        m+=1
    while t <= ti*(m-1) and a <= ai*(m-1):
        m-=1
    t,a=ti*m,ai*m
print(t+a)

Solution (Python):

import math
from decimal import *
N = int(input())
A, B = (1, 1)
for tmp in range (N):
    t, a = map(int,input().split())
    n = Decimal(max([math.ceil(A/t),math.ceil(B/a)]))
    A = n*t
    B = n*a
print(A+B)

Solution (Python):
import math
from decimal import Decimal
N = int(input())
T = [0 for i in range(N)]
A = [0 for i in range(N)]
for i in range(N):
	T[i], A[i] = map(int, input().split())

minT = T[0]
minA = A[0]

for i in range(1, N):
	tmpT = T[i]
	tmpA = A[i]
	
	rate = Decimal(max(math.ceil(minT/tmpT), math.ceil(minA/tmpA)))
	
		
		
	minT = tmpT*rate
	minA = tmpA*rate
print(minT+minA)

Solution (Python):
N = int(raw_input())
TA = [map(int, raw_input().split()) for _ in range(N)]
nt, na = 1, 1
for t, a in TA:
    xt = nt / t
    if nt % t != 0:
        xt += 1
    xa = na / a
    if na % a != 0:
        xa += 1
    x = max(xt, xa)
    nt, na = t*x, a*x
print nt + na

Solution (Python):
from collections import defaultdict
from itertools import count
from math import ceil
from fractions import Fraction

def main():
    n = int(input())
    A, B = map(int, input().split())
    for _ in range(n - 1):
        t, a = map(int, input().split())
        n = ceil(max(Fraction(A, t), Fraction(B, a)))
        A, B = n * t, n * a

    print(A + B)


if __name__ == '__main__':
    main()

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

T = []
A = []

for n in range(N):
	t,a = [int(x) for x in raw_input().split(" ")]
	T.append(t)
	A.append(a)

cntA = A[0]
cntT = T[0]

for i in range(N-1):
	if A[i+1] < cntA or T[i+1] < cntT:
		x = -(-cntA // A[i+1]) 
		y = -(-cntT // T[i+1])

		cntA = max(x,y) * A[i+1]
		cntT = max(x,y) * T[i+1]


	else:
		cntA = A[i+1]
		cntT = T[i+1]

print cntA + cntT

Solution (Python):
import math

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = 1
b = 1
for i in range(n):
    
    n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1)
    a = n * ta[i][0]
    b = n * ta[i][1]

print(a+b)

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

A = B = 1

for _ in xrange(n):
    a, b = map(int, sys.stdin.readline().split())
    k = max(B/b,A/a)
    while k * a < A or k * b < B:
        k += 1
    A= k*a
    B= k*b
print A+B

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

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

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

Solution (Python):
n = int(input())
t = 1
a = 1
for i in range(n):
    T, A = map(int, input().split())
    k = max(1, t // T + (t % T != 0), a // A + (a % A != 0))
    t = k * T
    a = k * A
print(t + a)

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

Solution (Python):

import math

def f(n,m):
    return n//m + (0 if n%m==0 else 1)

N=int(input())
T,A=1,1
for i in range(N):
    t_i,a_i=list(map(int,input().split()))

    if T<=t_i and A<=a_i:
        T,A=t_i,a_i
    else:
        raito=max(f(T,t_i),f(A,a_i))
        T,A=t_i*raito,a_i*raito

print(T+A)

Solution (Python):
N = int(input())
l = 1
r = 1

for k in range(N):
	T, A = map(int, input().split())
	if l % T != 0:
		l += (T - l % T)
	if r % A != 0:
		r += (A - r % A)

	if l//T == r//A:
		()
	elif l//T > r//A:
		r = (l//T) * A
	else:
		l = (r//A) * T
print(l+r)

Solution (Python):
from math import ceil
from fractions import Fraction


def main():
    N = int(input())
    t, a = 1, 1
    for _ in range(N):
        _t, _a = map(int, input().split())
        n = ceil(max(Fraction(t, _t), Fraction(a, _a)))
        t, a = _t * n, _a * n
    print(t + a)

if __name__ == '__main__':
    main()

Solution (Python):
import math
from decimal import Decimal


def main():
    N = int(input())
    t, a = 1, 1
    for _ in range(N):
        _t, _a = map(int, input().split())
        n = Decimal(max(math.ceil(t / _t), math.ceil(a / _a)))
        t, a = _t * n, _a * n

    print(t + a)

if __name__ == '__main__':
    main()

Solution (Python):


def f(n,d):
 if n%d==0:
  return n/d
 else:
  return n/d+1
 
n=int(raw_input())
t0,a0=map(int,raw_input().split())
for i in range(n-1):
 tt,aa=map(int,raw_input().split())
 m=max(f(t0,tt),f(a0,aa))
 t0=tt*m
 a0=aa*m
print t0+a0

Solution (Python):


from math import *
from decimal import Decimal

N = int(input())
T, A = 1, 1

for i in range(N):
	t, a = list(map(int, input().split()))
	n = Decimal(max(ceil(T / t), ceil(A / a)))
	T = n * t
	A = n * a

print(T + A)

Solution (Python):
def f(t2,t1):
    return t2//t1 + (1 if t2 % t1 > 0 else 0)

n = int(input())
t,a = map(int,input().split())
for i in range(n-1):
    tn,an = map(int,input().split())
    k = max(f(t,tn), f(a, an))
    t,a = k*tn, k*an
print(t+a)

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

Tn=1
An=1

for i in range(N):
    T_res=Tn%T[i]
    A_res=An%A[i]
    if T_res==0:
        T_q=Tn/T[i]
    else:
        T_q=(Tn+T[i]-T_res)/T[i]
    if A_res==0:
        A_q=An/A[i]
    else:
        A_q=(An+A[i]-A_res)/A[i]

    q=max(T_q,A_q)

    Tn=q*T[i]
    An=q*A[i]
        
        
print Tn+An

Solution (Python):
t, a = 1, 1
for i in range(input()):
    tn, an = map(int, raw_input().split())
    mlt = max(-(-t // tn), -(-a // an))
    t, a = tn * mlt, an * mlt
print t + a

Solution (Python):
def larger(x, y):
	if x > y:
		return x
	else:
		return y

def main():
	n = int(raw_input())
	tmp = raw_input().split()
	tmpt = int(tmp[0])
	tmpa = int(tmp[1])
	for i in range(1, n):
		inpt = raw_input().split()
		inptt = int(inpt[0])
		inpta = int(inpt[1])
		trate = tmpt / inptt
		if tmpt % inptt != 0:
			trate += 1
		arate = tmpa / inpta
		if tmpa % inpta != 0:
			arate += 1
		rate = larger(trate, arate)
		tmpt = inptt * rate
		tmpa = inpta * rate

	print (tmpt + tmpa)

main()

Solution (Python):
p=q=1
for i in range(0,int(raw_input())):
 r,s=map(int,raw_input().split())
 t=max((p+r-1)/r,(q+s-1)/s)
 p=r*t
 q=s*t
print p+q

Solution (Python):
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1.0
ah = 1.0

def f1(a,b):
     if a%b == 0:
          return a/b
     else:
          return a//b + 1

while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(f1(th,x),f1(ah,y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(int(th+ah))

Solution (Python):
import math
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1
ah = 1
while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max((th+x-1)//x, (ah+y-1)//y)
     th = m*x
     ah = m*y
     h += 1
print(th+ah)

Solution (Python):
import math
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1
ah = 1
while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(math.ceil(th/x),math.ceil(ah/y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(th+ah)

Solution (Python):
n = input()

t, a = 1, 1

for i in range(n):
    xs = map(int, raw_input().split())
    m = max((t + xs[0] - 1) / xs[0], (a + xs[1] - 1) / xs[1])
    t, a = xs[0] * m, xs[1] * m

print t + a

Solution (Python):

from math import ceil
N = int(input())
T = [[int(i) for i in input().split()] for n in range(N)]
m = T[0]

def hoge(a, b):
    if a%b==0:
        return a//b
    else:
        return a//b+1

for n in range(1, N):
    a = max(hoge(m[0],T[n][0]), hoge(m[1],T[n][1]))
    m = [T[n][0] * a, T[n][1] * a]
print(sum(m))

Solution (Python):


import sys

n = int(sys.stdin.readline())
A = B = 1

for _ in xrange(n):
    a, b = map(int, sys.stdin.readline().split())
    k = max(B/b, A/a)
    while k * b < B or k * a < A:
        k += 1
    A = k * a
    B = k * b
print A + B

Solution (Python):
try:
    N = int(raw_input())
    ab = map(int, raw_input().split(" "))
    a = ab[0]
    b = ab[1]
    for i in range(N-1):
      ab = map(int, raw_input().split(" "))
      A = ab[0]
      B = ab[1]
      if (a < A and b < B):
        a = A
        b = B
      else:
        if (-(-a/A) > -(-b/B)):
          a = A*(-(-a/A))
          b = B*(-(-a/A))
        else:
          b = B*(-(-b/B))
          a = A*(-(-b/B))
    print a+b
except EOFError:
    pass

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

t, a = map(int,input().split())
vote1 = t
vote2 = a

for i in range(n - 1):
    t, a = map(int,input().split())

    num1 = (vote1 + t - 1) // t
    num2 = (vote2 + a - 1) // a

    if num1 >= num2:
        vote1 = num1 * t
        vote2 = num1 * a
    else:
        vote1 = num2 * t
        vote2 = num2 * a

print(vote1 + vote2)

Solution (Python):
N = int(input())
T = []
A = []
for _ in range(N):
    Ti, Ai = map(int, input().split())
    T.append(Ti)
    A.append(Ai)

tmp_t = T[0]
tmp_a = A[0]
ans = tmp_t + tmp_a
for i in range(1, N):
    n_t = tmp_t // T[i] if tmp_t % T[i] == 0 else tmp_t // T[i] + 1
    n_a = tmp_a // A[i] if tmp_a % A[i] == 0 else tmp_a // A[i] + 1
    n = max(n_t, n_a)
    tmp_t = T[i] * n
    tmp_a = A[i] * n
    ans = tmp_t + tmp_a

print(ans)

Solution (Python):
n = int(raw_input())
ta_list = []
x, y = 1, 1
for i in range(n):
    
    t, a = map(int, raw_input().split())
    k = max((x+t-1)/t, (y+a-1)/a)
    x = k*t
    y = k*a

print x + y

Solution (Python):
from fractions import gcd
N = int(raw_input())
t = a = 1
for _ in xrange(N):
    T, A = map(int, raw_input().split())
    q = max((t + T - 1) / T, (a + A - 1) / A)
    t, a = T * q, A * q
print t + a

Solution (Python):
import math
n = int(input())
c_t = 0
c_a = 0
for i in range(n):
    t, a = [int(x) for x in input().split(" ")]
    
    init = int(max(c_t // t, c_a // a, 1))
    for j in range(init,10**18):
        if t*j >= c_t and a*j >= c_a:
            c_t = t*j
            c_a = a*j
            
            break
print(c_t + c_a)

Solution (Python):
from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = int(x / r)
    while n * r > x:
        n -= 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)

Solution (Python):
from sys import stdin
n = int(stdin.readline())
a = []
b = []
for _ in xrange(n):
 x,y = map(int,stdin.readline().split())
 a.append(x)
 b.append(y)
x = a[0]
y = b[0]
for i in xrange(1,n):
 fir = a[i]
 sec = b[i]
 if fir>=x and sec >= y:
  x = fir;y=sec
 elif fir>=x:
  k = y/sec
  if y%sec:
   k+=1
  x = fir * k
  y = sec * k
 elif sec>=y:
  k = x/fir
  if x%fir:
   k += 1
  x = fir * k
  y = sec * k
 else:
  u = x/fir
  if x%fir:
   u+=1
  v = y/sec
  if y%sec:
   v+=1
  k = u
  if v > k:
   k = v
  x = fir * k
  y = sec * k



print x + y

Solution (Python):
n = int(raw_input())
t = 1
a = 1
for i in range(n):
    x, y = map(int, raw_input().split())
    tmp = max(
        t / x if t % x == 0 else t / x + 1,
        a / y if a % y == 0 else a / y + 1
    )
    t = x * tmp
    a = y * tmp
print t+a

Solution (Python):
N = int(input())
vote = [1,1]
for i in range(N):
    ratio = list(map(int, input().split()))
    for j in range(2):
        while(vote[j] % ratio[j] != 0):
            vote[j] += 1
    if vote[0] * ratio[1] < vote[1] * ratio[0]:
        vote[0] = vote[1] // ratio[1] * ratio[0];
    if vote[0] * ratio[1] > vote[1] * ratio[0]:
        vote[1] = vote[0] // ratio[0] * ratio[1];
print(vote[0] + vote[1])

Solution (Python):
def f1(a,b):
    if a%b==0:
        return a//b
    else:
        return a//b+1

n=int(input())
t=1
a=1
for i in range(n):
    ti,ai = map(int,input().split())
    k=max(f1(t,ti),f1(a,ai))
    t=ti*k
    a=ai*k
print(t+a)

Solution (Python):
import math                                             
from decimal import Decimal                             
                                                        
N = input()                                             
t = []                                                  
a = []                                                  
for i in range(int(N)):                                 
    t_n, a_n = input().split()                          
    t.append(Decimal(t_n))                              
    a.append(Decimal(a_n))                              
                                                        
t_ans = 0                                               
a_ans = 0                                               
for t_n, a_n in zip(t, a):                              
    k = max(math.ceil(t_ans/t_n), math.ceil(a_ans/a_n)) 
    if not k:                                           
        k = 1                                           
    t_ans = Decimal(k*t_n)                              
    a_ans = Decimal(k*a_n)                              
print(t_ans+a_ans)

Solution (Python):

import math
from decimal import Decimal

N = int(input())

votes = []

for _ in range(N):
    votes.append([Decimal(n) for n in input().split()])

befa = 1
befb = 1

for a, b in votes:
    kakeru = Decimal(max(math.ceil(befa / a), math.ceil(befb / b)))
    befa = a * kakeru
    befb = b * kakeru

print(int(befa)+int(befb))

Solution (Python):
def f(x,y):
    return x//y + (1 if x%y > 0 else 0)
n = int(input())
a,b = list(map(int,input().split()))
for i in range(n-1):
    c,d = list(map(int,input().split()))
    e = max(f(a,c),f(b,d))
    a,b = c*e,d*e
print(a+b)

Solution (Python):
n=int(raw_input())
t=a=1

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

Solution (Python):
def f(x,y):
    return x//y + (1 if x%y > 0 else 0)
n = int(input())
a,b = list(map(int,input().split()))
for i in range(n-1):
    c,d = list(map(int,input().split()))
    e = max(f(a,c),f(b,d))
    a,b = c*e,d*e
print(a+b)

Solution (Python):
p=q=1
for i in[0]*input():t,a=map(int,raw_input().split());k=max(~-p/t,~-q/a)+1;p=t*k;q=a*k
print p+q

Solution (Python):
N = int(raw_input())
X = [map(int, raw_input().split()) for i in range(N)]

def update(n, x):
    t, a = x
    n1, n2 = n
    c = 1
    i0 = max(n1/t, n2/a)
    for i in xrange(i0, 10**18):
        if i * t >= n1 and i * a >=n2:
            c = i
            break
    return c * t, c* a

n = (1, 1)
for x in X:
    n = update(n, x)
print(sum(n))

Solution (Python):

ans = 0

for i in range(int(input())):
    t_i, a_i = list(map(lambda x: int(x), input().split()))

    if i == 0:
        t, a = t_i, a_i

    else:
        n = max((t + t_i - 1) // t_i, (a + a_i - 1) // a_i)
        t = n*t_i
        a = n*a_i

    ans = t + a

print(ans)

Solution (Python):
import math
from decimal import Decimal

N = int(input())
T, A = [Decimal(x) for x in input().split()]

for i in range(1,N):
        T2, A2 = [Decimal(x) for x in input().split()]
        n = Decimal(max(math.ceil(T/T2),math.ceil(A/A2)))
        T = T2 * n
        A = A2 * n

print(T+A)

Solution (Python):
import sys
import math
from decimal import Decimal
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return int(a)
def lcm(a,b):
    return int(a*b/gcd(a,b))

lines = sys.stdin.readlines()
n = int(lines[0])
ret = [1,1]
before_sum = 2
before_ret = [ret[0],ret[1]]
for line in lines[1:]:
    line = line.rstrip().split(" ")
    for l in range(len(line)):
        line[l] = int(line[l])
    
    
    
    
    a,b = int(line[0]),int(line[1])
    
    if (ret[0]<=a) and (ret[1]<=b):
        ret[0]=a
        ret[1]=b
    else:
        check_a = Decimal(ret[0])/Decimal(a)
        check_b = Decimal(ret[1])/Decimal(b)
        if (check_a>check_b):
            ret[0]=math.ceil(check_a)*line[0]
            ret[1]=math.ceil(check_a)*line[1]
        elif (check_a<=check_b):
            ret[0]=math.ceil(check_b)*line[0]
            ret[1]=math.ceil(check_b)*line[1]
    
    
    
    
    """
    if (before_sum>(ret[0]+ret[1])):
        
        check_ret = [ret[0],ret[1]]
        i=2
        print ("check:",check_ret,before_ret)
        while((check_ret[0]+check_ret[1])<before_sum):
            check_ret[0]=ret[0]*i
            check_ret[1]=ret[1]*i
            i+=1
        i=2
        while(check_ret[0]<before_ret[0] or check_ret[1]<before_ret[1]):
            check_ret[0]=ret[0]*i
            check_ret[1]=ret[1]*i
            i+=1
        ret[0] = check_ret[0]
        ret[1] = check_ret[1]
        before_sum=ret[0]+ret[1]
    else:
        before_sum=ret[0]+ret[1]
    """



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

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

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

Solution (Python):
time=input()

aok=1
tak=1

for i in range(time):
	l=map(int, raw_input().split())
	if aok<tak:
		if tak%l[1]!=0:
			tak=(tak/l[1]+1)*l[1]
		if aok>tak/l[1]*l[0]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			aok=tak/l[1]*l[0]
	elif aok==tak:
		if l[0]<=l[1]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
	else:
		if aok%l[0]!=0:
			aok=(aok/l[0]+1)*l[0]
		if tak>aok/l[0]*l[1]:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
		else:
			tak=aok/l[0]*l[1]
print aok+tak

Solution (Python):
N = int(raw_input())
t = [[0,0] for i in range(N)]
for i in range(N):
    l = []
    l = raw_input().split()
    t[i][0] = int(l[0])
    t[i][1] = int(l[1])
min_ = [0,0]
min_[0] = t[0][0]
min_[1]= t[0][1]
for i in range(1,N):

    cnt_0 = min_[0]/t[i][0]
    if min_[0]%t[i][0]!=0:
        cnt_0+=1
    cnt_1 = min_[1]/t[i][1]
    if min_[1]%t[i][1]!=0:
        cnt_1+=1
    cnt = max(cnt_0,cnt_1)
    min_[0] = cnt*t[i][0]
    min_[1] = cnt*t[i][1]
print min_[0]+min_[1]

Solution (Python):
from math import ceil
from fractions import Fraction

n = int(input())
sa, st = 1, 1

for a, t in (map(int, input().split()) for _ in range(n)):
    r = ceil(max(Fraction(sa, a), Fraction(st, t)))
    sa, st = a * r, t * r

print(sa + st)

Solution (Python):
import math
from fractions import Fraction

n = int(input())
t, a = [int(x) for x in input().split()]
for i in range(1, n):
    t2, a2 = [int(x) for x in input().split()]
    x = math.ceil(max(Fraction(t, t2), Fraction(a, a2)))
    t, a = x * t2, x * a2

print(t + a)

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

ans = [0, 0]
T, A = [0] * 1001, [0] * 1001

for i in range(N):
    T[i], A[i] = map(int, raw_input().split())

    if i != 0 and T[i - 1] - T[i] > 0 or A[i - 1] - A[i] > 0:

        if (T[i  - 1] / T[i]) > (A[i - 1] / A[i]):
            m  = T[i  - 1] / T[i]
            if T[i - 1] % T[i] != 0:
                m += 1 

        else:
            m = A[i - 1] / A[i]
            if A[i - 1] % A[i] != 0:
                m += 1

        T[i] *= m
        A[i] *= m

    ans = [T[i], A[i]]

print sum(ans)

Solution (Python):
from random import random
import math
import re
from fractions import Fraction

N = int(input())
ca, cb = 0, 0
for _ in range(N):
    a, b = map(int, input().split(" "))
    if ca == 0 and cb == 0:
        ca, cb = a, b
    else:
        r = int(math.ceil(max(Fraction(ca, a), Fraction(cb,b))))
        
        ca, cb = a*r, b*r
        
print (ca + cb)

Solution (Python):
import math
N = input()
datas = []
for _ in range(N):
	data = map(long, raw_input().split(" "))
	datas.append(data)

t_min = datas[0][0]
o_min = datas[0][1]
for _ in range(N-1):
	t = datas[_+1][0]
	o = datas[_+1][1]
	t_mul = t_min/t + 1 if t_min%t != 0 else t_min/t
	o_mul = o_min/o + 1 if o_min%o != 0 else o_min/o
	if t_mul < o_mul:
		t_min = o_mul*t
		o_min = o_mul*o
	else:
		t_min = t_mul*t
		o_min = t_mul*o

print t_min+o_min

Solution (Python):




N=int(input())

hihyo=[]
for idx in range(0,N,1):
    mojir=input()
    hyo=mojir.split(' ')
    hihyo.append((int(hyo[0]),int(hyo[1])))

taka=hihyo[0][0]
aoki=hihyo[0][1]

for idx in range(1,N,1):

    takahi= taka//hihyo[idx][0]  + (0 if  taka%hihyo[idx][0]==0 else 1)
    aokihi= aoki//hihyo[idx][1]  + (0 if  aoki%hihyo[idx][1]==0 else 1)


    k=max(takahi,aokihi)
    taka=k*hihyo[idx][0]
    aoki=k*hihyo[idx][1]

ans=taka+aoki
print(ans)

Solution (Python):
N = input()
T,A = map(int,raw_input().split(' '))
for i in xrange(N-1):
    t,a = map(int,raw_input().split(' '))
    s1 = T/t
    if T%t != 0:
        s1+=1
    s2 = A/a
    if A%a != 0:
        s2+=1
    s = max(s1,s2)
    T = s*t
    A = s*a
print T+A

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())


def join(s):
    return ''.join(s)


def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)


def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m


def index(a, x):
    
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])



n=i()
t=[0]*n
a=[0]*n
for j in range(n):
    t[j],a[j]=ii()

tt,aa=1,1
for j in range(n):
    if t[j]>=tt and a[j]>=aa:
        tt,aa=t[j],a[j]
    else:
        k=max(tt/t[j]+int(tt%t[j]!=0),aa/a[j]+int(aa%a[j]!=0))
        tt,aa=t[j]*k,a[j]*k

print tt+aa

Solution (Python):
def getLnInput():
    return input().split()


def getNewVote(currentVote, newRatio):
    multFacCeil = []
    for i in range(2):
        multFacCeil.append((currentVote[i] - 1) // newRatio[i] + 1)
    newVote = []
    maxMF = max(multFacCeil)
    for i in range(2):
        newVote.append(newRatio[i] * maxMF)
    return newVote


def main():
    N = int(getLnInput()[0])
    voteNum = list(map(int, getLnInput()))
    for i in range(N - 1):
        newRatio = list(map(int, getLnInput()))
        voteNum = getNewVote(voteNum, newRatio)
    print(sum(voteNum))
    return


main()

Solution (Python):
from sys import stdin

n = int(stdin.readline())

m = 10 ** 18 + 7


t_votes, a_votes = (int(x) for x in stdin.readline().split())

p_t, p_a = t_votes, a_votes

for _ in range(n-1):
    t, a = (int(x) for x in stdin.readline().split())
    if (t, a) == (p_t, p_a):
        continue
    for i in range(max(t_votes // t, a_votes // a) - 1, m):
        t_v, a_v = t * i, a * i
        if t_v >= t_votes and a_v >= a_votes:
            break
    t_votes, a_votes = t_v, a_v
    p_t, p_a = t, a

print(t_votes + a_votes)

Solution (Python):
N = int(raw_input())
Ts = []
As = []
for t in xrange(N):
    T, A = map(int, raw_input().split())
    Ts.append(T)
    As.append(A)
    
leastT= Ts[0]
leastA= As[0]

for i in xrange(1,len(Ts)):
    maxcoeff = max( (leastA + As[i] - 1) / As[i], 
                    (leastT + Ts[i] - 1) /Ts[i])
    leastT = Ts[i] * maxcoeff
    leastA = As[i] * maxcoeff

print leastT+leastA

Solution (Python):
N = int(raw_input())
Ts = []
As = []
for t in xrange(N):
    T, A = map(int, raw_input().split())
    Ts.append(T)
    As.append(A)
    
leastT= Ts[0]
leastA= As[0]

for i in xrange(1,len(Ts)):
    maxcoeff = max( (leastA + As[i] - 1) / As[i], 
                    (leastT + Ts[i] - 1) /Ts[i])
    leastT = Ts[i] * maxcoeff
    leastA = As[i] * maxcoeff

print leastT+leastA

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