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



Sample input:
3
2 3
1 1
3 2


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

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

for i in range(N-1):
    t,a = map(int, input().split())
    tmp1,tmp2 = t,a
    # 比はそのままで、あり得る投票数まで値を増やす
    while t < T or a < A:
        t += tmp1
        a += tmp2
    T = t
    A = a

print(T + A)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x, y = [int(i) for i in input().split()]

for i in range(n-1):
  t, a = [int(i) for i in input().split()]
  
  if t >= x and a >= y:
    x = t
    y = a

  else:
    c = 2
    while True:
      x_ = t * c
      y_ = a * c
      if x_ >= x and y_ >= y:
        break
      c += 1
      
    x, y = x_, y_
    
print(x+y)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = []
a = []

for i in range(0, n):
    ti, ai = [int(_) for _ in input().split()]
    t.append(ti)
    a.append(ai)

newest_t = t[0]
newest_a = a[0]

for i in range(0, n):
    div_t = newest_t // t[i]
    div_a = newest_a // a[i]

    for j in range(min(div_t, div_a)-1, max(div_t, div_a)+2):
        if j * t[i] >= newest_t and j * a[i] >= newest_a:
            newest_t = j * t[i]
            newest_a = j * a[i]
            break

print(newest_t + newest_a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = []
a = []

for i in range(0, n):
    ti, ai = [int(_) for _ in input().split()]
    t.append(ti)
    a.append(ai)

newest_t = t[0]
newest_a = a[0]

for i in range(0, n):
    tmin = t[i]
    amin = a[i]
    while True:
        if tmin >= newest_t and amin >= newest_a:
            newest_t = tmin
            newest_a = amin
            break
        else:
            tmin += t[i]
            amin += a[i]

print(newest_t + newest_a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

dp = [0] * N
for i in range(N):
    a, t = map(int, input().split())

    if i == 0:
        dp[0] = (a, t)
        continue

    j = 1
    while True:
        tmp = (a * j, t * j)
        if (dp[i - 1][0] <= tmp[0]) and (dp[i - 1][1] <= tmp[1]):
            dp[i] = (a * j, t * j)
            break
        j += 1

print(dp[N-1][0] + dp[N-1][1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ta = []
for i in range(n):
    ta.append([int(i) for i in input().split()])

for i in range(1, n):
    tmp = ta[i][:]
    while ta[i-1][0] > ta[i][0] or ta[i-1][1] > ta[i][1]:
        ta[i][0] += tmp[0]
        ta[i][1] += tmp[1]

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
rates = [list(map(int, input().split(' '))) for _ in range(N)]
candT = rates[0][0]
candA = rates[0][1]
for T, A in rates:
    if T * candA == A * candT:
        continue
    else:
        flag = 0
        i = 1
        while flag == 0:
            if T * i - candT >= 0 and A * i - candA >= 0:
                candT = T * i
                candA = A * i
                flag = 1
            i += 1
print(candT + candA)

Submission status: Time Limit Exceeded

Solution code:
N =int(input())

T1=[]
T2=[]
s=input().split()
T1.append(int(s[0]))
T2.append(int(s[1]))

for i in range(1,N):
  s=input().split()
  n=1
  while(T1[i-1] > n*int(s[0]) or T2[i-1] > n*int(s[1]) ):
         n+=1
   
  T1.append(n*int(s[0]))
  T2.append(n*int(s[1]))

print(T1[N-1]+T2[N-1])

Submission status: Time Limit Exceeded

Solution code:
N =int(input())

T1=[]
T2=[]

for i in range(N):
  s=input().split()
  n=1
  if i!=0:
     while(True):
      if T1[i-1] > n*int(s[0]) or T2[i-1] > n*int(s[1]):
         n+=1
      else:
         break
  T1.append(n*int(s[0]))
  T2.append(n*int(s[1]))

print(T1[N-1]+T2[N-1])

Submission status: Time Limit Exceeded

Solution code:
N =int(input())

T1=[]
T2=[]

for i in range(N):
  s=input().split()
  n=1
  if i!=0:
     while(True):
      if T1[i-1] > n*int(s[0]) or T2[i-1] > n*int(s[1]) or T1[i-1]+T2[i-1] > n*int(s[0])+n*int(s[1]):
         n+=1
      else:
         break
  T1.append(n*int(s[0]))
  T2.append(n*int(s[1]))

print(T1[N-1]+T2[N-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = []
a = []
for i in range(0,N):
	tokuhyousuu = list(map(int,input().split()))
	t.append(tokuhyousuu[0])
	a.append(tokuhyousuu[1])

T = t[0]
A = a[0]
r = 1
r_2 = 1

for j in range(0,N):
	if(T<=t[j] and A<=a[j]):
		T = t[j]
		A = a[j]

	elif(T>t[j] and A>a[j]):
		for k in range(1000000000000000000000000):
			if(T<=(k*t[j])):
				r = k
				break

		for l in range(1000000000000000000000000):
			if(A<=(l*a[j])):
				r_2 = l
				break

		T = t[j]*(max(r,r_2))
		A = a[j]*(max(r,r_2))


	elif(T>t[j]):
		for p in range(1000):
			if(T<=(p*t[j])):
				T = p*t[j]
				A = p*a[j]
				break

	elif(A>a[j]):
		for q in range(1000):
			if(A<=(q*a[j])):
				T = q*t[j]
				A = q*a[j]
				break
print(T+A)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[0.0,0.0]
for i in range(n):
  a0,b0=x
  a ,b =[int(i) for i in input().split()]
  if a>=b:
    while a0/a!=a0//a or a0==0 or (a0/a)*b<b0 :
      a0+=1
    x=[a0,(a0/a)*b]
  else:
    while b0/b!=b0//b or b0==0 or (b0/b)*a<a0 :
      b0+=1
    x=[(b0/b)*a,b0]
print(int(sum(x)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

now = nex = 1
for i in range(0, N - 1):
    nex = 1
    while True:
        if now * rates[i][0] <= nex * rates[i + 1][0] and now * rates[i][1] <= nex * rates[i + 1][1]:
            break
        nex += 1
    now = nex
print((rates[-1][0] + rates[-1][1]) * nex)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

array = [[int(x) for x in input().split()] for x in range(n)]

taka = array[0][0]
ao = array[0][1]

for item in array[1:]:
    taka_tmp = item[0]
    ao_tmp = item[1]

    cnt = 1
    while True:
        if taka_tmp*cnt >= taka and ao_tmp*cnt >= ao:
            taka = taka_tmp*cnt
            ao = ao_tmp*cnt
            break
        cnt += 1
print(ao+taka)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t,a = map(int,input().split())
for i in range(n-1):
  T,A=map(int,input().split())
  count = 0
  while (A*count < a) or (T*count < t):
    count += 1
  a = count * A
  t = count * T
print(a+t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

t,a = src[0]
for ti,ai in src[1:]:
    tn = t + (ti - t%ti)%ti
    an = tn // ti * ai
    while an < a:
        tn += ti
        an += ai
    t,a = tn,an
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n = int(input())
nums = [list(map(int,input().split())) for _ in range(n)]
a, b = nums[0][0], nums[0][1]
for i in range(1, n):
    if a / nums[i][0] != b / nums[i][1]:
        p, q = nums[i][0], nums[i][1]
        if a > p or b > q:
            j = 2
            while p < a or q < b:
                p = nums[i][0] * j
                q = nums[i][1] * j
                j += 1
        a, b = p, q
        
print(a + b)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n = int(input())
nums = [list(map(int,input().split())) for _ in range(n)]
a, b = nums[0][0], nums[0][1]
for i in range(1, n):
    if a / nums[i][0] != b / nums[i][1]:
        p, q = nums[i][0], nums[i][1]
        while p < a or q < b:
            p += nums[i][0]
            q += nums[i][1]
        a, b = p, q
        
print(a + b)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  times=min(t//c,a//d)
  e,f=c*times,d*times
  while(e<t or f<a):
    #print(e,f)
    times+=1
    e,f=c*times,d*times
    #print(e,f)
  t,a=e,f
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  e,f=c,d
  times=1
  while(e<t or f<a):
    #print(e,f)
    times+=1
    e,f=c*times,d*times
    #print(e,f)
  t,a=e,f
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = 0
r = 0
for i in range(n):
    a,b = map(int,input().split())
    g = a
    h = b
    while a < t or b < r:
        a += g
        b += h
    t = a
    r = b
print(a + b)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a_min=1
b_min=1
for i in range(N):
  a,b=map(int,input().split())
  cnt=1
  while True:
    if a_min<=a*cnt and b_min<=b*cnt:
      break
    cnt+=1
  a_min=a*cnt
  b_min=b*cnt
print(a_min+b_min)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]

ans = 0
pre_t = 0
pre_a = 0

for t, a in TA:
    gcdd = gcd(t, a)

    t = t * gcdd
    a = a * gcdd

    first_t = t
    first_a = a

    while (pre_t > t) or(pre_a > a):
        t += first_t
        a += first_a

    pre_t = t
    pre_a = a

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
T, A = map(int, input().split())
for i in range(n - 1):
    t, a = map(int, input().split())
    t_, a_ = t, a
    while t < T or a < A:
        t += t_
        a += a_
    T, A = t, a
print(T + A)

Submission status: Time Limit Exceeded

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

t = ta[0][0]
a = ta[0][1]

for i in range(n):
    tt = ta[i][0]
    aa = ta[i][1]
    while t > tt or a > aa:
        tt += ta[i][0]
        aa += ta[i][1]
    t = tt
    a = aa

print(t+a)

Submission status: Time Limit Exceeded

Solution code:
num_times_checked = int(input())
votes_t = 0
votes_a = 0
for i in range(num_times_checked):
    vals = input().split(' ')
    ratio = (int(vals[0]), int(vals[1])) # T:A
    if (votes_t + votes_a == 0):
        votes_t = ratio[0]
        votes_a = ratio[1]
    else:
        new_t = ratio[0]
        new_a = ratio[1]
        while (new_t < votes_t or new_a < votes_a):
            new_t += ratio[0]
            new_a += ratio[1] 
        votes_t = new_t
        votes_a = new_a

print(str( votes_t + votes_a ))

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
t = 1
a = 1
for _ in range(n):
    i,j = map(int, raw_input().split())
    x = i
    y = j
    while(x < t or y < a):
        x += i
        y += j
    t = x
    a = y
print t+a

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

t_num , a_num = map(int, input().split())

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

ans = t_num + a_num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t,a=map(int,input().split())
for i in range(n-1):
    ti,ai=map(int,input().split())
    tii,aii,m=ti,ai,1
    while tii*m < t or aii*m < a:
        m+=1
    t,a=tii*m,aii*m
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
N = int(input())
TA = []
counter = 0
for tmp in range (N):
    TA.append(list(map(int,input().split())))

whole = TA[0][0] + TA[0][1] #総和
for tmp in range (1,N):
    counter = 0
    tmp2 = TA[tmp][0]+TA[tmp][1]
    before = whole/(TA[tmp-1][0]+TA[tmp-1][1]) #比の数値1が何票か。
    while True:
        if (whole+counter)%tmp2 != 0:
            counter += tmp2 - (whole+counter)%tmp2
        whole += counter
        if (before*TA[tmp-1][0] > ((whole/tmp2)*TA[tmp][0]) or (before*TA[tmp-1][1] > ((whole/tmp2)*TA[tmp][1]))):
            counter = 1
            continue
        else:
            break
print(whole)

Submission status: Time Limit Exceeded

Solution code:
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]
	while tmpT<minT or tmpA<minA:
		tmpT = tmpT+T[i]
		tmpA = tmpA+A[i]
	minT = tmpT
	minA = tmpA
print(minT+minA)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import count


def main():
    n = int(input())
    A, B = map(int, input().split())
    for _ in range(n - 1):
        t, a = map(int, input().split())
        for n in count(1):
            if n * t >= A and n * a >= B:
                A, B = n * t, n * a
                break
    print(A + B)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = ta[0][0]
b = ta[0][1]
for i in range(1, n):
    tempa = ta[i][0]
    tempb = ta[i][1]
    j = 2
    while(tempa < a or tempb < b):
        tempa = ta[i][0] * j
        tempb = ta[i][1] * j
        j += 1

    a = tempa
    b = tempb

print(a+b)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = 0
a = 0
for i in range(n):
    T, A = map(int, input().split())
    k = 1
    while True:
        if T * k >= t and A * k >= a:
            t = T * k
            a = A * k
            break
        else:
            k += 1
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
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):
    n=1
    while True:
        if Tn>n*T[i] or An>n*A[i]:
            n=2*n

        else:
            break
    n=n/2
    while True:
        if Tn>n*T[i] or An>n*A[i]:
            n+=1

        else:
            break
    
            
    
    Tn=n*T[i]
    An=n*A[i]

print Tn+An

Submission status: Time Limit Exceeded

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

Tn=0 
An=0

for i in range(N):
    n=1
    while True:
        if Tn>n*T[i] or An>n*A[i]:
            n+=1

        else:
            break
    Tn=n*T[i]
    An=n*A[i]

print Tn+An

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 1
li = list[0]
thh = int(li[0])
ahh = int(li[1])
while h < n:
     listh = list[h]
     listhh = list[h-1]
     th = int(listh[0])
     ah = int(listh[1])
     l = 1
     m = 1
     while l*th < thh:
        l += 1
     while m*ah < ahh:
        m += 1
     a = max(l,m)
     thh = th*a
     ahh = ah*a
     h += 1
print(thh+ahh)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 1
listh = list[h]
listhh = list[h-1]
th = int(listh[0])
thh = int(listhh[0])
ah = int(listh[1])
ahh = int(listhh[1])
while h < n:
     listh = list[h]
     listhh = list[h-1]
     th = int(listh[0])
     ah = int(listh[1])
     l = 1
     m = 1
     while l*th < thh:
        l += 1
     while m*ah < ahh:
        m += 1
     if l>m:
        thh = th*l       
        ahh = ah*l
     else:
        thh = th*m
        ahh = ah*m
     h += 1
print(thh+ahh)

Submission status: Time Limit Exceeded

Solution code:
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 = 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)

Submission status: Time Limit Exceeded

Solution code:
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(" ")]
    #print(min(c_t / t, c_a / a))
    init = int(math.ceil(max(min(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
            #print("->" + str(j))
            break
print(c_t + c_a)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
T = []
A = []
for _ in xrange(N):
    t, a = map(int, raw_input().split())
    T.append(t)
    A.append(a)

ans = T[0] + A[0]
tmpT = T[0]
tmpA = A[0]
for i in xrange(1, N):
    if T[i] >= T[i-1] and A[i] >= A[i-1] and T[i] + A[i] >= ans:
        ans = T[i] + A[i]
        tmpT = T[i]
        tmpA = A[i]
    else:
        add = T[i] + A[i]
        j = ans / add + 1
        while True:
            tmpAns = add * j
            tt = T[i] * j
            aa = A[i] * j
            if tt >= tmpT and aa >= tmpA:
                ans = tmpAns
                tmpT =tt
                tmpA = aa
                break
            j += 1
print ans

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

def update(rt, ra, t, a):
    while rt * a != ra * t:
        if rt * a < ra * t:
            a = int(ceil(ra * t / rt))
        else:
            t = int(ceil(rt * a / ra))
    return t, a

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]

for i in range(1, n):
    t, a = update(data[i][0], data[i][1], t, a)

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c_t = 0
c_a = 0
for i in range(n):
    t, a = [int(x) for x in input().split(" ")]
    for j in range(1,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)

Submission status: Time Limit Exceeded

Solution code:
def update(rt, ra, t, a):
    while rt * a != ra * t:
        if rt * a < ra * t:
            a += 1
        else:
            t += 1
    return t, a

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]

for i in range(1, n):
    t, a = update(data[i][0], data[i][1], t, a)

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
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]:
        while (vote[0] * ratio[1] != vote[1] * ratio[0]):
            vote[0] += 1;
    if vote[0] * ratio[1] > vote[1] * ratio[0]:
        while (vote[0] * ratio[1] != vote[1] * ratio[0]):
            vote[1] += 1;
print(vote[0] + vote[1])

Submission status: Time Limit Exceeded

Solution code:
N = input()                                                            
t = []                                                                 
a = []                                                                 
for i in range(int(N)):                                                
    t_n, a_n = input().split()                                         
    t.append(int(t_n))                                                 
    a.append(int(a_n))                                                 
                                                                       
ma = 0                                                                 
t_prev = 0                                                             
a_prev = 0                                                             
for t_n, a_n in zip(t, a):                                             
    summ = t_n + a_n                                                   
    summ_cp = summ                                                     
    i = 0                                                              
    while 1:                                                           
        i += 1                                                         
        summ = summ_cp * i                                             
        if summ >= ma and ((t_n*i) >= t_prev) and ((a_n*i) >= a_prev): 
            ma = summ                                                  
            break                                                      
        #summ = summ_cp * i                                            
    t_prev = t_n*i                                                     
    a_prev = a_n*i                                                     
print(ma)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N = int(input())

votes = []

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

# an = votes[0][0]
# bn = votes[0][1]
#
# for a, b in votes:
#     if a == b :
#         an = bn = max(an, bn)
#     elif a < b:
#         az = a
#         while(a)
#     elif a > b:

sum = 0
befa = 0
befb = 0

for a, b in votes:
    a_m = a
    b_m = b
    while(a < befa or b < befb):
        a += a_m
        b += b_m
    t = a + b;
    i = 1
    while(t * i < sum):
        i += 1
    sum = t * i
    befa = a
    befb = b

print(sum)

Submission status: Time Limit Exceeded

Solution code:
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
    for i in xrange(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))

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr
n = int(input())
t=1
a=1
for i 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:
        at=a_
        while True:
            a_=a_+at
            if a_>=a:
                a=a_
                t=int(t_*a/at)
                break
    elif t_<t and a_>=a:
        tt=t_
        while True:
            t_=t_+tt
            if t_>=t:
                t=t_
                a=int(a_*t/tt)
                break
    else:
        tt=t_
        at=a_
        while True:
            t_=t_+tt
            a_=a_+at
            if t_>=t and a_>=a:
                t=t_
                a=a_
                break
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ta = []
for i in range(n):
    t, a = map(int, input().split())
    ta.append((t, a))
min_t, min_a = ta[0]
sum_poll = min_t + min_a

x_ = 1
for poll in ta:

    t_, a_ = poll
    while(True):
        tmp_t, tmp_a = t_ * x_, a_ * x_

        if tmp_t >= min_t and tmp_a >= min_a: 
            min_t = tmp_t
            min_a =  tmp_a
            sum_poll = tmp_t + tmp_a
            x_ = 1
            break
        x_ += 1
print(sum_poll)

Submission status: Time Limit Exceeded

Solution code:
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 = 1
    while cnt*t[i][0]<min_[0] or cnt*t[i][1]<min_[1]:
        cnt = cnt+1
    min_[0] = cnt*t[i][0]
    min_[1] = cnt*t[i][1]
print min_[0]+min_[1]

Submission status: Time Limit Exceeded

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

for i in range(n):
    x,y=map(int,raw_input().split())
    if t<=x and a<=y:
        t=x
        a=y
    else:
        tmp=min(t/x,a/y)
        while 1:
            if x*tmp>=t and y*tmp>=a:
                t=x*tmp
                a=y*tmp
                break
            tmp+=1
print t+a
exit()

Submission status: Time Limit Exceeded

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

for i in range(n):
    x,y=map(int,raw_input().split())
    if t<=x and a<=y:
        t=x
        a=y
    else:
        tmp=min(t/x,y/a)
        while 1:
            if x*tmp>=t and y*tmp>=a:
                t=x*tmp
                a=y*tmp
                break
            tmp+=1
print t+a
exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

t = 0
a = 0
for i in range(n):
    T, A = list(map(int, input().split()))
    if i == 0:
        t = T
        a = A
    else:
        x = 1
        nt = T * x
        na = A * x
        while True:
            if t <= nt and a <= na:
                t = nt
                a = na
                break
            else:
                x += 1
                nt = T * x
                na = A * x

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
    sm = 0
    while True:
        if (c - b * sm) % (a - b) == 0:
            x = (c - b * sm) // (a - b)
            if 0 <= x <= sm:
                return x, sm - x
        sm += 1

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, y = solve(a2, -t2, a * t2 - t * a2)
    t, a = t + x, a + y

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
d=[]
k=0
for j in range(a):
 d.append([int(i) for i in input().split()])
s=d[0]
for j in range(1,a):
     aa=[0,0]
     flag=1
     if d[j][0]>=s[0] and d[j][1]>=s[1]:
        s[0]=d[j][0]
        s[1]=d[j][1]
    
     else:
         while flag:
           aa[0]+=d[j][0]
           aa[1]+=d[j][1]
           if aa[0]>=s[0] and aa[1]>=s[1]:
               flag=0
               s=aa
               break
        
print(s[0]+s[1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
for i in range(n):
    r = list(map(int, input().split()))
    if i == 0:
        t = r[0]
        a = r[1]
    else:
        r0 = r[0]
        r1 = r[1]
        while 1:
            if r[0] >= t and r[1] >= a:
                t = r[0]
                a = r[1]
                break
            r[0] += r0
            r[1] += r1
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
    sm = 0
    while True:
        for x in range(sm + 1):
            if x * a + (sm - x) * b == c:
                return x, (sm - x)
        sm += 1

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, y = solve(a2, -t2, a * t2 - t * a2)
    t, a = t + x, a + y

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
def solve(t,a,tp,ap):

    if t/a == tp/ap:
        return t,a
    
    next_t=0
    next_a=0
    while next_t < t or next_a < a:
        next_t += tp
        next_a += ap
    return next_t,next_a


N = int(raw_input())
l = []
for i in range(N):
    l.append( map(float,raw_input().split()) )

t = 1.0
a = 1.0

while len(l):
    tp,ap = l.pop(0)
    t,a = solve(t,a,tp,ap)

print int(t+a)

Submission status: Time Limit Exceeded

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

for i in range(n):
    x,y=map(int,raw_input().split())
    if t<=x and a<=y:
        t=x
        a=y
    else:
        tmp=1
        while 1:
            if x*tmp>=t and y*tmp>=a:
                t=x*tmp
                a=y*tmp
                break
            tmp+=1
print t+a

Submission status: Time Limit Exceeded

Solution code:
import re
import doctest


class IO_for_Contest(object):
    @staticmethod
    def my_input():
        # return raw_input()
        return input()

    @staticmethod
    def read_from_input():
        n = IO_for_Contest.read_int()
        t = []
        a = []
        for i in range(n):
            buf = IO_for_Contest.read_n_int(2)
            t.append(buf[0])
            a.append(buf[1])
        return t, a

    @staticmethod
    def read_line():
        return IO_for_Contest.my_input().strip()

    @staticmethod
    def read_int():
        return int(IO_for_Contest.my_input().strip())

    @staticmethod
    def read_n_int(n):
        return list(map(
                    int,
                    re.split('\s+', IO_for_Contest.my_input().strip())))[: n]


def solve():
    buf = IO_for_Contest.read_from_input()
    t = buf[0]
    a = buf[1]
    min_number_of_vote = get_min_number_of_vote(t, a)
    print(sum(min_number_of_vote))


def get_min_number_of_vote(t, a):
    vote_t = 1
    vote_a = 1
    for i in range(len(t)):
        buf = get_estimate_of_next_vote(vote_t, vote_a, t[i], a[i])
        # print(buf)
        vote_t = buf[0]
        vote_a = buf[1]
    return vote_t, vote_a


def get_estimate_of_next_vote(vote_t, vote_a, ratio_t, ratio_a):
    # simple case
    if vote_t % ratio_t == 0 and vote_a % ratio_a == 0:
        if vote_t // ratio_t == vote_a // ratio_a:
            return vote_t, vote_a
    offset = 0
    while True:
        new_vote_t = vote_t + offset
        if new_vote_t % ratio_t == 0:
            if (new_vote_t // ratio_t) * ratio_a >= vote_a:
                return new_vote_t, (new_vote_t // ratio_t) * ratio_a
            else:
                offset += ratio_t
        else:
            offset += 1

if __name__ == '__main__':
    # doctest.testmod()
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
for i in range(n):
    r = list(map(int, input().split()))
    if i == 0:
        t = r[0]
        a = r[1]
    else:
        j = 1
        while 1:
            if r[0]*j >= t and r[1]*j >= a:
                t = r[0]*j
                a = r[1]*j
                break
            j += 1
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [input().split(' ') for i in range(N)]

preA = int(arr[0][0])
preB = int(arr[0][1])
if N != 1:
    for i in range(N):
        N = 1
        A = int(arr[i][0])
        B = int(arr[i][1])
        tmpA = A
        tmpB = B

        while preA > tmpA or preB > tmpB:
            N = N+1
            tmpA = A*N
            tmpB = B*N
        preA = tmpA
        preB = tmpB      
print(preA + preB)

Submission status: Time Limit Exceeded

Solution code:
N = input()
datas = []
for _ in range(N):
	data = map(int, raw_input().split(" "))
	datas.append(data)

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

	while o_mul*o < o_min:
		o_mul+=1

	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