Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    n, q = map(int, input().split())
    s = input()

    res = [None]*q

    for i in range(q):

        l, r = map(int, input().split())
        count = 0

        for point in range(l-1, r-1):
            if s[point:point+2] == 'AC':
                count += 1

        res[i] = count

    for i in range(q):
        print(res[i])


main()


Fixed submission:
def main():

    n, q = map(int, input().split())
    s = input()

    cumsum = [0]*n
    for i in range(n-1):
        if s[i:i+2] == 'AC':
            cumsum[i+1] = cumsum[i] + 1
        else:
            cumsum[i+1] = cumsum[i]

    res = [None]*q

    for i in range(q):

        l, r = map(int, input().split())
        res[i] = cumsum[r-1] - cumsum[l-1]

    for i in range(q):
        print(res[i])


main()
Buggy python submission (verdict: Runtime Error):
import math

N, K = map(int, input().split())
p = 0

for i in range(1, min(K, N + 1)):
    print(math.ceil(math.log2(K / i)))
    p += 2 ** (-math.ceil(math.log2(K / i)))

p += max(0, N - K + 1)
print(p / N)


Fixed submission:
import math

N, K = map(int, input().split())
p = 0

count = 1
while True:
    p += max(0, min(N + 1, math.ceil(K / 2 ** (count - 1))) - math.ceil(K / 2 ** count)) * 0.5 ** count
    count += 1
    if K / 2 ** count < 0.5:
        break

p += max(0, N - K + 1)
print(p / N)
Buggy python submission (verdict: Runtime Error):
x=input()
a=input()

if a>x:
    print(0)
else:
    print(10)


Fixed submission:
[x,a]=[int(i) for i in input().split()]

if a>x:
    print(0)
else:
    print(10)
Buggy python submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n && sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)


Fixed submission:
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n and sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy python submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)


Fixed submission:
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n and sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy python submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(1)

while sum+l[count-1]<=x:
    sum=sum+l[count-1]
    count=count+1
    
print(count)


Fixed submission:
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n and sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy python submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(1)

while sum+l[count-1]<=x:
    sum=sum+l[count-1]
    count=count+1
    print(sum)
    print(count)


print(count)


Fixed submission:
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n and sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)
Buggy python submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(double(w*h/2)+" "+a)


Fixed submission:
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(str(w*h/2)+" "+str(a))

Buggy python submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]


if x*2==w and y*2==h:
    ans=int(1)
else ans=int(0)

print(double(w*h/2)+" "+ans)


Fixed submission:
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(str(w*h/2)+" "+str(a))

Buggy python submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]


if x*2=w and y*2=h:
    ans=int(1)
else ans=int(0)

print(double(w*h/2)+" "+ans)


Fixed submission:
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(str(w*h/2)+" "+str(a))

Buggy python submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]

print(double(w*h/2))
if x*2=w and y*2=h:
    print(1)
else print(0)


Fixed submission:
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(str(w*h/2)+" "+str(a))
Buggy python submission (verdict: Runtime Error):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

import math

def fac(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N, K = nl()
prev_a = 0
prev_b = 0
for i in range(1, K+1):
    print(fac(N-K+1, i) * fac(K-1, i-1) % 1000000007)



Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

import math

def fac(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N, K = nl()
prev_a = 0
prev_b = 0
for i in range(1, K+1):
    print(fac(N-K+1, i) * fac(K-1, i-1) % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)




Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)
Buggy python submission (verdict: Runtime Error):
import heapq
from collections import defaultdict

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

edges = defaultdict(set)
ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

h = []
for i in range(N):
    heapq.heappush(h, (ranks[i], i))

for i in range(N):
    rank, node = heapq.heappop(h)
    ds[node] = cs[i]
    for next_node in edges[node]:
        heapq.heappush(h, (ranks[next_node]-1, next_node))
        edges[next_node].remove(node)

print(M)
print(' '.join([str(d) for d in ds]))


Fixed submission:
import heapq
from collections import defaultdict

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

edges = defaultdict(set)
ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

h = []
for i in range(N):
    heapq.heappush(h, (ranks[i], i))

for i in range(N):
    rank, node = heapq.heappop(h)
    ds[node] = cs[i]
    for next_node in edges[node]:
        ranks[next_node] -= 1
        heapq.heappush(h, (ranks[next_node], next_node))
        edges[next_node].remove(node)

print(M)
print(' '.join([str(d) for d in ds]))
Buggy python submission (verdict: Runtime Error):
N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = [(u, v)]
while len(queue) > 0:
    u, v = queue.pop(0)
    vertices[u] = True
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v] and not edges[u][v]:
        colors[v] = 1 - colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

for i in range(1, N+1):
    print(colors[i])

Fixed submission:
from collections import defaultdict

N = int(input())

colors = [0] * (N+1)
vertices = defaultdict(bool)
edges = defaultdict(dict)
for i in range(1, N):
    u, v, w = map(int, input().split())
    edges[u][v] = w % 2 == 0
    edges[v][u] = w % 2 == 0
    vertices[u] = False
    vertices[v] = False

queue = []
for v in edges[u].keys():
    queue.append((u, v))
vertices[u] = True

while len(queue) > 0:
    u, v = queue.pop(0)
    if vertices[v]:
        continue
    vertices[v] = True
    if colors[u] == colors[v]:
        if not edges[u][v]:
            colors[v] = 1 - colors[u]
    else:
        if edges[u][v]:
            colors[v] = colors[u]

    for nv in edges[v].keys():
        if not vertices[nv]:
            queue.append((v, nv))

for i in range(1, N+1):
    print(colors[i])
Buggy python submission (verdict: Runtime Error):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from math import gcd      #3.5
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_left[1], gcds_right[N-2]))


Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from fractions import gcd
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_right[1], gcds_left[N-2]))

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))

max_g = As[1]
for i in range(2, N):
    max_g = gcd(As[i], max_g)

for i in range(1, N):
    g = As[0]
    for j in range(1, N):
        if j == i:
            continue
        g = gcd(As[j], g)
    max_g = max(max_g, g)

print(max_g)

Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from fractions import gcd
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_right[1], gcds_left[N-2]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

black = 0
black_counts = []
white = 0
white_counts = []
for i in range(N):
    if S[i] == '#':
        black += 1
    black_counts.append(black)

    if S[-1-i] == '.':
        white += 1
    white_counts.insert(0, white)

min_count = min(black_counts[N-1], white_counts[0])
for i in range(N-1):
    min_count = min(min_count, black_counts[i] + white_counts[i+1])
print(min_count)

Fixed submission:
N = int(input())
S = input()

black = 0
black_counts = [0]*N
white = 0
white_counts = [0]*N
for i in range(N):
    if S[i] == '#':
        black += 1
    black_counts[i] = black

    if S[-1-i] == '.':
        white += 1
    white_counts[N-1-i] = white

min_count = min(black_counts[N-1], white_counts[0])
for i in range(N-1):
    min_count = min(min_count, black_counts[i] + white_counts[i+1])
print(min_count)
Buggy python submission (verdict: Time Limit Exceeded):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()
S = s()

nums = []

num = 1
prev = S[0]
first_zero = prev == '0'
for i in range(1, N):
    if prev != S[i]:
        nums.append(num)
        num = 1
        prev = S[i]
    else:
        num += 1
nums.append(num)

first = 0
if first_zero:
   first = -1

res = 0
for i in range(first, len(nums), 2):
    total = sum(nums[max(i, 0):min(i+2*K+1, len(nums))])
    if total > res:
        res = total

print(res)





Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()
S = s()

nums = [0]

num = 1
prev = S[0]
first_zero = prev == '0'
for i in range(1, N):
    if prev != S[i]:
        nums.append(num)
        num = 1
        prev = S[i]
    else:
        num += 1
nums.append(num)

total = 0
for i in range(len(nums)):
    total += nums[i]
    nums[i] = total

first = 0
if first_zero:
   first = -1

res = 0
for i in range(first, len(nums), 2):
    total = nums[min(i+2*K+1, len(nums)-1)] - nums[max(i, 0)]
    if total > res:
        res = total

print(res)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

counts = defaultdict(int)
numbers = {}

cities = []
for i in range(M):
    p, y = map(int, input().split())
    cities.append([i, p, y])

sorted_cities = sorted(cities, key=lambda x: x[2])
for city in sorted_cities:
    i, p, y = city
    counts[p] += 1
    numbers[i] = '{:06}{:06}'.format(p, counts[p])

for city in cities:
    print(numbers[city[0]])

Fixed submission:
from collections import defaultdict
N, M = map(int, input().split())

counts = defaultdict(int)
numbers = {}

cities = []
for i in range(M):
    p, y = map(int, input().split())
    cities.append([i, p, y])

sorted_cities = sorted(cities, key=lambda x: x[2])
for city in sorted_cities:
    i, p, y = city
    counts[p] += 1
    numbers[i] = '{:06}{:06}'.format(p, counts[p])

for city in cities:
    print(numbers[city[0]])
Buggy python submission (verdict: Runtime Error):
N = int(input())
points = []
for i in range(N):
    x, y, h = map(int, input().split())
    points.append([x, y, h])

def height(cx, cy):
    res = set()
    for p in points:
        if p[2] == 0:
            continue
        res.add(p[2] + abs(p[0] - cx) + abs(p[1] - cy))
    return list(res)

def find():
    result = []
    for x in range(101):
        for y in range(101):
            hs = height(x, y)
            if len(hs) == 1:
                result.append([str(x), str(y), str(hs[0])])
    return result

res = find()
if len(res) > 1:
    raise Exception()

print(' '.join(res[0]))

Fixed submission:
N = int(input())
points = []
f = None
for i in range(N):
    x, y, h = map(int, input().split())
    if h > 0:
        f = [x, y, h]
    points.append([x, y, h])

def height(cx, cy):
    H = f[2] + abs(f[0] - cx) + abs(f[1] - cy)
    for p in points:
        if p[2] != max(H - abs(p[0] - cx) - abs(p[1] - cy), 0):
            return 0
    return H

for x in range(101):
    for y in range(101):
        h = height(x, y)
        if h > 0:
            print(' '.join([str(x), str(y), str(h)]))
Buggy python submission (verdict: Runtime Error):

from math import gcd      #3.5
def lcm(x, y):
    return (x * y) // gcd(x, y)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
common = n()
for i in range(N-1):
    common = lcm(common, n())

print(common)



Fixed submission:

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
common = n()
for i in range(N-1):
    common = lcm(common, n())

print(common)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

import sys

teiki = defaultdict(set)
for i in range(M):
    a, b = map(int, input().split())
    teiki[a].add(b)


if 1 not in teiki:
    print('IMPOSSIBLE')
    sys.exit()

for i in teiki[1]:
    if i in teiki and N in teiki[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Fixed submission:
from collections import defaultdict

N, M = map(int, input().split())

import sys

teiki = defaultdict(set)
for i in range(M):
    a, b = map(int, input().split())
    teiki[a].add(b)


if 1 not in teiki:
    print('IMPOSSIBLE')
    sys.exit()

for i in teiki[1]:
    if i in teiki and N in teiki[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

dp = [0] * (X+1)
dp[1] = 1
for i in range(2, X+1):
    j = dp[i-1]
    if dp[i - j] < dp[i-1]:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+1
print(dp[X])


Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

for x in range(1, X):
    if x * (x + 1) // 2 >= X:
        print(x)
        import sys
        sys.exit()

print(X)

Buggy python submission (verdict: Runtime Error):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

dp = [0] * (X+1)
dp[1] = 1
for i in range(2, X+1):
    if dp[i - dp[i-1]] < dp[i-1]:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+1
print(dp[X])


Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

for x in range(1, X):
    if x * (x + 1) // 2 >= X:
        print(x)
        import sys
        sys.exit()

print(X)

Buggy python submission (verdict: Runtime Error):
INF = float("inf")
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

dp = [0] * (X+1)
dp[1] = 1
for i in range(2, X+1):
    if dp[i - dp[i-1]] < dp[i-1]:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+1

print(dp[X])


Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

for x in range(1, X):
    if x * (x + 1) // 2 >= X:
        print(x)
        import sys
        sys.exit()

print(X)
Buggy python submission (verdict: Time Limit Exceeded):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
p = 1
for i in range(N):
    p *= i+1
print(p % 1000000007)


Fixed submission:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
p = 1
for i in range(N):
    p *= i+1
    p %= 1000000007
print(p)
Buggy python submission (verdict: Runtime Error):
x, y = map(int, input().split())

if abs(x) == abs(y):
    print(1)
elif abs(x) < abs(y):
    if y > 0:
        if x >= 0:
            print(abs(x - y))
        else:
            print(abs(x - y) + 1)
    else:
        if x >= 0:
            print(abs(x - y) + 1)
        else:
            print(abs(x - y) + 2)
else:
    if x < 0:
        if y <= 0:
            print(abs(x - y))
        else:
            print(abs(x - y) + 1)
    else:
        if y <= 0:
            print(abs(x - y) + 1)
        else y >= 0:
            print(abs(x - y) + 2)

Fixed submission:
x, y = map(int, input().split())

if abs(x) == abs(y):
    print(1)
elif abs(x) < abs(y):
    if y > 0:
        if x >= 0:
            print(abs(y) - abs(x))
        else:
            print(abs(y) - abs(x) + 1)
    else:
        if x >= 0:
            print(abs(y) - abs(x) + 1)
        else:
            print(abs(y) - abs(x) + 2)
else:
    if x < 0:
        if y <= 0:
            print(abs(x) - abs(y))
        else:
            print(abs(x) - abs(y) + 1)
    else:
        if y <= 0:
            print(abs(x) - abs(y) + 1)
        else:
            print(abs(x) - abs(y) + 2)
Buggy python submission (verdict: Runtime Error):
import math

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

def min_vote(index):
    if index == N-1:
        return ratios[N-1-index]

    mt, ma = min_vote(index+1)
    t, a = ratios[N-1-index]
    min_ratio = max(math.ceil(mt / t), math.ceil(ma / a))
    return [t * min_ratio, a * min_ratio]

print(sum(min_vote(0)))

Fixed submission:
import math

N = int(input())
pt = 1
pa = 1
for i in range(N):
    t, a = map(int, input().split())

    t_ratio = pt // t
    a_ratio = pa // a
    if pt % t != 0:
        t_ratio += 1
    if pa % a != 0:
        a_ratio += 1
    min_ratio = max(t_ratio, a_ratio)
    pt = t * min_ratio
    pa = a * min_ratio

print(pt+pa)