Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import statistics

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

L=0
R=0
DDT = 0
ans = 0
for K in range(statistics.median_low(d)-min(d),statistics.median_low(d)+max(d)):
    for i in range(N):
        if d[i] == K:
            DDT += 1
        elif d[i] < K:
            L += 1
        else:
            R += 1
    if L == R:
        ans += 1
    else:
        while DDT > 0:
            if L < R:
                L += 1
                DDT -= 1
            elif L > R:
                R += 1
                DDT -= 1
            else:
                L += 1
                DDT -= 1
        if L == R:
            ans += 1
    L = 0
    R = 0
    DDT = 0
print(ans-1)

### FIXED CODE ###

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

d.sort()

ans = d[N//2] - d[(N//2)-1]
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
n_list = []
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n*(n-1))//2
print(ans)
### BUGGY CODE ###

N = int(input())
D = [int(_) for _ in input().split()]
M = int(input())
T = [int(_) for _ in input().split()]

D = sorted(D)
T = sorted(T)
Dstart = 0
flag = True

for i in T:
    for j in D[Dstart:]:
        Dstart += 1
        if i == j:
            break
        elif i < j:
            flag = False
            break
        if Dstart == N:
            flag = False
    if not flag:
        break

print("YES" if flag else "NO")

### FIXED CODE ###

N = int(input())
D = [int(_) for _ in input().split()]
M = int(input())
T = [int(_) for _ in input().split()]

D = sorted(D)
T = sorted(T)
Tindex = 0
flag = False

for i in D:
    if i == T[Tindex]:
        Tindex += 1
        if Tindex == M:
            flag = True
            break

print("YES" if flag else "NO")
### BUGGY CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l, (stk[0][1], stk[0][2]))
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll, v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    heappush(ll, v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    # heapify(l)
    # heappush(l, (stk[0][1], stk[0][2]))
    l = [(stk[0][1], stk[0][2])]
    for i in range(1, n):
        ll = []
        #heapify(ll)
        for j in range(len(l)):
            # v = heappop(l)
            v = l[j]
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    # heappush(ll, v)
                    ll.append(v)
        # heappush(ll, stk[i][1:])
        ll.append(stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

class SegTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [set() for i in range(2 * self.N - 1)]

    def update(self, index, char):
        i = self.N - 1 + index
        self.tree[i] = set(char)

        while i > 0:
            i = (i - 1) // 2
            left = self.tree[i * 2 + 1]
            right = self.tree[i * 2 + 2]
            self.tree[i] = left | right

    def get(self, a, b):
        return self.query(a, b, 0, 0, self.N)

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()

        if a <= l and r <= b:
            return self.tree[k]

        left = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
        right = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
        return left | right


def solve():

    N = int(input())
    tree = SegTree(N)

    S = list(input())
    for i in range(N):
        tree.update(i, S[i])

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == '1':
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        elif t_q == '2':
            l_q = int(in_1)
            r_q = int(in_2)
            print(len(tree.get(l_q-1, r_q)))


solve()


### FIXED CODE ###

class SegTree:

    def __init__(self, N, S):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [0 for i in range(2 * self.N - 1)]
        for i in range(len(S)):
            self.tree[self.N - 1 + i] = 1 << (ord(S[i]) - ord('a'))
        for i in range(self.N - 2, -1, -1):
            self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

    def update(self, index, char):
        i = self.N - 1 + index
        self.tree[i] = 1 << (ord(char) - ord('a'))

        while i > 0:
            i = (i - 1) // 2
            self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

    def get(self, a, b):
        return self.query(a, b, 0, 0, self.N)

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.tree[k]
        else:
            left = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            right = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return left | right


def solve():

    N = int(input())
    S = list(input())
    tree = SegTree(N, S)

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == '1':
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        elif t_q == '2':
            l_q = int(in_1)
            r_q = int(in_2)
            print(bin(tree.get(l_q-1, r_q)).count('1'))


solve()
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(a) for a in input().split()])

def AC(S):
    num = 0
    c = 0
    while num <= len(S)-2:
        if S[num] == "A" and S[num+1] == "C":
            c += 1
        num += 1
    return c

ANS = []
for j in range(Q):
    Temp = S[L[j][0]-1:L[j][1]]
    print(AC(Temp))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(x) for x in input().split()])
    
ac_list = [0 for i in range(N)]
ac_num = 0
for i in range(1, N):
    pre = S[i-1]
    ac_list[i] = ac_list[i-1]
    if pre == "A" and S[i] == "C":
        ac_num += 1
        ac_list[i] = ac_num

for i in range(Q):
    ans = ac_list[L[i][1]-1] - ac_list[L[i][0]-1]
    print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))

    ans = 0
    max_i = 0
    max_value = 0
    for i in range(N):
        t = 0
        for k in range(i, i+K):
            if len(p) > k:
                t += p[k]
            else:
                break
        if max_value < t:
            max_value = t
            max_i = i

    for i in range(max_i, max_i+K):
        if len(p) <= i:
            break
        n = p[i] + 1
        ans += (n*(n-1)//2) / (n-1)
    
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))

    r = [0]
    for i in range(N):
        r.append(r[i]+p[i])


    ans = 0
    max_i = 0
    max_value = 0
    for i in range(1,N-K+1):
        t = r[i+K]-r[i]
        if max_value < t:
            max_value = t
            max_i = i



    for i in range(max_i, max_i+K):
        if len(p) <= i:
            break
        n = p[i] + 1
        ans += (n*(n-1)//2) / (n-1)
    
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

A=[]
B=[]

for _ in range(M):
  n, m = map(int, input().split())
  A.append(n)
  B.append(m)

roomN = ['N' for _ in range(N)]
roomN[0] = 1
roomPN = [0 for _ in range(N)]

for order in range(2, N+1):
  if order-1 in roomN:
     pres = [i+1 for i,x in enumerate(roomN) if x == order-1]
  for pre in pres:
    if pre in A:
      indexs = [i for i,x in enumerate(A) if x == pre]
      for index in indexs:
        now = B[index] -1
        if roomN[now] == 'N':
          roomN[now] = order
          if roomPN[now] == 0:
            roomPN[now] = pre
    if pre in B:
      indexs = [i for i,x in enumerate(B) if x == pre]
      for index in indexs:
        now = A[index] -1
        if roomN[now] == 'N':
          roomN[now] = order
          if roomPN[now] == 0:
            roomPN[now] = pre

print('Yes')
for i in range(1, N):
  print(roomPN[i])

### FIXED CODE ###

from collections import deque

n,m=map(int,input().split())

graph=[[] for i in range(n)]

roomSign=[-1]*n

for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if roomSign[i] == -1:
          roomSign[i]=v
          D.append(i)

print("Yes")

for i in range(1,n):
    print(roomSign[i]+1)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]
    inf = 10**9+7

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] = dp[i-1] + dp[i-2]
        
        dp[i] %= inf

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

S=input()
ACGT=['A','C','G','T']
ans=[]
k=0
while k<len(S):
    num=0
    if S[k] in ACGT:
        num=1
        for i in range(1,len(S)-k):
            if S[k+i] in ACGT:
                num+=1
            else:
                break
    ans.append(num)
    k=+num

print(max(ans))

### FIXED CODE ###

S=input()
ACGT=['A','C','G','T']
ans=[0]
k=0
while k<len(S):
    num=0
    if S[k] in ACGT:
        num=1
        for i in range(1,len(S)-k):
            if S[k+i] in ACGT:
                num+=1
            else:
                break
        ans.append(num)
    else:
        num=1
    k+=num

print(max(ans))
### BUGGY CODE ###

nums = list(map(int, input().split()))
n = nums[0]
k = nums[1]

def absolute(n,k):
    return abs(n-k)

x = absolute(n, k)
if n < x:
    print(n)
else:
    while absolute(x, k) < x:
        x = absolute(x, k)

    print(x)

### FIXED CODE ###

nums = list(map(int, input().split()))
n = nums[0]
k = nums[1]

def absolute(n,k):
    return abs(n-k)

x = absolute(n, k)
if n % k == 0:
    print(0)
elif n < x:
    print(n)
else:
    while absolute(x, k) < x:
        x = x % k
        x = absolute(x, k)

    print(x)
### BUGGY CODE ###

k=int(input())


k9=k*9
l=10
for n in range(1,k9+5):
    if l*7%k9==7%k9:
        print(n)
        break
    l=l*10%k9
else:
    print(-1)

### FIXED CODE ###

k=int(input())
k9=k*9
l=10
for n in range(1,k+5):
    if l*7%k9==7%k9:
        print(n)
        break
    l=l*10%k9
else:
    print(-1)
### BUGGY CODE ###

from collections import defaultdict
import copy

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

COST = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
A.sort(key=lambda x: COST[x])


class Num:
    def __init__(self):
        self.nums = defaultdict(int)

    def __lt__(self, rhs):
        nd1 = sum(self.nums.values())
        nd2 = sum(rhs.nums.values())
        if nd1 < nd2:
            return True
        elif nd1 > nd2:
            return False
        keys = set(self.nums.keys()) | set(rhs.nums.keys())
        for n in sorted(keys, reverse=True):
            if self.nums[n] < rhs.nums[n]:
                return True
            elif self.nums[n] > rhs.nums[n]:
                return False
        return False

    def __add__(self, rhs):
        obj = copy.deepcopy(self)
        obj.nums[rhs] += 1
        return obj

    def __repr__(self):
        if not self.nums:
            return 0
        s = []
        for k in sorted(self.nums.keys(), reverse=True):
            s.extend([str(k)] * self.nums[k])
        return ''.join(s)


best = [None for _ in range(N + 1)]
best[0] = Num()
for n in range(N + 1):
    for a in A:
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = best[before] + a
        if best[n] is None:
            best[n] = val
        else:
            best[n] = max(val, best[n])

print(best[N])

### FIXED CODE ###

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


COST = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
A = sorted(A, reverse=True)

best = [None for _ in range(N + 1)]
best[0] = tuple([0] * len(A))
for n in range(N + 1):
    for ai, a in enumerate(A):
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = tuple(x + (1 if i == ai else 0) for i, x in enumerate(best[before]))
        if (
            best[n] is None
            or sum(best[n]) < sum(val)
            or (sum(best[n]) == sum(val) and best[n] < val)
        ):
            best[n] = val
print(''.join(sorted(''.join(str(d) * n for d, n in zip(A, best[N])), reverse=True)))
### BUGGY CODE ###

import math

def is_prime(n):
    
    nmax = int(math.sqrt(n)) + 1
    for i in range(2, nmax):
        if(n%i)==0:
            return False
    return True

def pf(n):
    sn = int(math.sqrt(n)) + 1
    ps = []
    for i in range(1, sn):
        if (n%i)==0:
            ps.append(i)
            ps.append(int(n/i))
    del ps[0]
    return ps        

n = int(input())
ps = []
num = pf(n)
for i in num:
    if is_prime(i):
        ps.append(i)
        
zs = []        
for p in ps:
    z = p
    while(z<=n):
        zs.append(z)
        z *= p
zs.sort()

cnt = 0
for z in zs:
    if(n>1):
        if(n%z==0):
            n /= z
            cnt += 1
print(cnt)

### FIXED CODE ###

import math

def is_prime(n):
    if n==1:
        return False
    nmax = int(math.sqrt(n)) + 1
    for i in range(2, nmax):
        if(n%i)==0:
            return False
    return True

def pf(n):
    sn = int(math.sqrt(n)) + 1
    ps = []
    for i in range(1, sn):
        if (n%i)==0:
            ps.append(i)
            ps.append(int(n/i))
    del ps[0]
    return ps        

n = int(input())
ps = []
num = pf(n)
for i in num:
    if is_prime(i):
        ps.append(i)
        
zs = []        
for p in ps:
    z = p
    while(z<=n):
        zs.append(z)
        z *= p
zs.sort()

cnt = 0
for z in zs:
    if(n>1):
        if(n%z==0):
            n /= z
            cnt += 1
print(cnt)
### BUGGY CODE ###


def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    dp[n][c]=0
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())

w = [-1]; v = [-1]
size = n+1
dp = [ [None for i in range(c+1)] for j in range(n+1)]
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)        
        
        

### FIXED CODE ###

n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

print(dp[n-1][W])
### BUGGY CODE ###

import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort()
b.sort()
c.sort()

ans = 0

for up in a:
    tmp1 = bisect.bisect_right(b, up)
    for middle in b[tmp1:]:
        down = bisect.bisect_right(c, middle)
        ans += (n - down)
    
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort()
b.sort()
c.sort()

ans = 0

for middle in b:
    tmp1 = bisect.bisect_left(a, middle)
    tmp2 = bisect.bisect_right(c, middle)
    ans += tmp1 * (n - tmp2)

print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

cnt = 0
dist = [a[0]-1]
for ai in a[1:]:
    cnt += dist.count(-ai)
    dist.append(ai)
    dist = list(map(lambda x: x-1, dist))

print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

# i < j
# j - i = Aj + Ai
# j - Aj = i + Ai

ans = 0
adds = dict()
for j in range(n):
    sub = j - a[j]
    if sub in adds.keys():
        ans += adds[sub]

    add = j + a[j]
    if add in adds.keys():
        adds[add] += 1
    else:
        adds[add] = 1

print(ans)
### BUGGY CODE ###

def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

n = int(input())
ans = fib(n)

print(ans)

### FIXED CODE ###

def fib(n):
    f0, f1 = 1, 1

    for i in range(n - 1):
        f1, f0 = f1 + f0, f1

    return f1

n = int(input())
ans = fib(n)

print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

a2 = []
for _ in range(m):
    b, c = map(int, input().split())
    a2 += [c for _ in range(b)]
a2.sort()

for i in range(min(n, len(a2))):
    if a[i] < a2[-1-i]:
        a[i] = a2[-1-i]
    else:
        break

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(x)) for x in input().split()]

for _ in range(m):
    b, c = map(int, input().split())
    a += [(b, c)]

from operator import itemgetter
a = sorted(a, key=itemgetter(1))

ans = 0
t = 0
while n-t > 0:
    (k, x) = a.pop()
    ans += x * min(k, n-t)
    t += k

print(ans)
### BUGGY CODE ###

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

w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

dp=[[0 for i in range(W+1)] for _ in range(N+1)]

for i in range(0,N):
    for j in range(0,W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])

print(dp[N][W])


### FIXED CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(100111)] for j in range(111)]

for i in range(0,n):
    for sum_w in range(0,w+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

print(dp[n][w])
### BUGGY CODE ###

n=int(input())
s=input()
ans=n
for i in range(n):
    #i番目（0〜N-1）の人をリーダーにする
    
    #リーダの左で向きを変える人数(もともと西を向いてて、東に向き直らなければいけない人数)
    left_num=s[:i].count("W")
    
    #リーダの右で向きを変える人数(もともと東を向いてて、西に向き直らなければいけない人数）
    right_num=s[i+1:].count("E")
    
    num=left_num+right_num
    
    #ansを更新
    ans=min(ans,num)
    
print(ans)

### FIXED CODE ###

n=int(input())
s=input()

#Eが出てくる回数の累積和を取る(O(n))
l=[0]
l_tmp=0
for i in range(n):
    if s[i]=="E":
        l_tmp+=1
        l.append(l_tmp)
    else:
        l.append(l_tmp)

#クエリ(O(n))

ans=n
for j in range(1,n+1):
    #j番目より左のWの数は(j-1)-l[j-1]
    #j番目より右のEの数はl[-1]-l[j]
    ans=min(ans,(j-1)-l[j-1]+l[-1]-l[j])
    
print(ans)
### BUGGY CODE ###


import math

def read_input():
    n = int(input())

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

    return n, ratios


def get_votes(ex_votes, ratio):
    def check_votes(a, b):
        return a[0] <= b[0] and a[1] <= b[1]

    # cand1
    cand1 = list(ex_votes)
    a = ex_votes[0] % ratio[0]
    if a != 0:
        cand1[0] += ratio[0] - a
    cand1 = (cand1[0], int(cand1[0] / ratio[0] * ratio[1]))

    while not check_votes(ex_votes, cand1):
        cand1 = (cand1[0] + ratio[0], cand1[1] + ratio[1])


    cand2 = list(ex_votes)
    b = ex_votes[1] % ratio[1]
    if b != 0:
        cand2[1] += ratio[1] - b
    cand2 = (int(cand2[1] / ratio[1] * ratio[0]), cand2[1])

    while not check_votes(ex_votes, cand2):
        cand2 = (cand2[0] + ratio[0], cand2[1] + ratio[1])

    if sum(cand1) < sum(cand2):
        return cand1
    else:
        return cand2


def submit():
    n, ratios = read_input()

    votes = (1, 1)
    for ratio in ratios:
        votes = get_votes(votes, ratio)

    print(sum(votes))


if __name__ == '__main__':
    submit()

### FIXED CODE ###

import math


def read_input():
    n = int(input())

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

    return n, ratios


def get_votes(ex_votes, ratio):
    def check_votes(a, b):
        return a[0] <= b[0] and a[1] <= b[1]

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

    base = div_ceil(sum(ex_votes), (ratio[0] + ratio[1]))
    base = int(base)
    while True:
        test_votes = (ratio[0] * base, ratio[1] * base)
        if check_votes(ex_votes, test_votes):
            return test_votes
        else:
            diff_votes = (test_votes[0] - ex_votes[0], test_votes[1] - ex_votes[1])
            if diff_votes[0]/ratio[0] < diff_votes[1]/ratio[1]:
                base += div_ceil(-diff_votes[0], ratio[0])
            else:
                base += div_ceil(-diff_votes[1], ratio[1])
            base = int(base)


def submit():
    n, ratios = read_input()

    votes = ratios[0]
    for ratio in ratios[1:]:
        votes = get_votes(votes, ratio)

    print(sum(votes))


if __name__ == '__main__':
    submit()