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

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_c

def getMaxGCD(count,product):
	maxPossibleInt = int(float(product)**(1.0/float(count)))
	checkGCDRange = range(maxPossibleInt+1,0,-1)
	maxGCD = maxPossibleInt+1
	for i in checkGCDRange:
		powNumber = i**count
		amari = product % powNumber
		if amari == 0:
			maxGCD = i
			print(maxGCD)
			exit(0)
	return maxGCD

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	if n == 1:
		print(p)
		exit(0)
	if p == 1:
		print(1)
		exit(0)
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))

### FIXED CODE ###

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_a

def getMaxGCD(count,product):
	# getPrimeFunction
	primeSet = []  # リストの初期化
	maxCheckNumber = round(product ** (1 / 2))
	checkRange = range(2, maxCheckNumber + 1, 1)
	for i in checkRange:
		baseCount = 0
		while product % i == 0:
			baseCount = baseCount + 1
			product = product // i
		if  0 < baseCount:
			primeSet.append((i, baseCount))
# 二つを引数にしそれぞれ出力する
	if 1 < product:
		primeSet.append((product, 1))

	gcdNumber = 1
	for baseCount,powNumber in  primeSet:
		gcdNumber = gcdNumber * (baseCount ** ( powNumber // count))
	return gcdNumber

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	if n == 1:
		print(p)
		exit(0)
	if p == 1:
		print(1)
		exit(0)
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
import sys
vals = [None]*n
def quest(q):
    print(q)
    sys.stdout.flush()
    res = input()
    if res=="Vacant":
        exit()
        res = -1
    elif res=="Male":
        res = 1
    else:
        res = 0
    vals[q] = res
    return res

k = n//2
res1 = quest(0)
res2 = quest(k)

if (res2-res1)%2 != k%2:
    l = 1
    r = k
elif (res2-res1):
    l = k+1
    r = n-1
    
while l<r+1:
    m = (l+r)//2
    res = quest(m)
    if (res-vals[l])%2 != (l-m)%2:
        r = m-1
    else:
        l = m+1
quest(l)
quest(r)

### FIXED CODE ###

import sys
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
import sys
vals = [None]*n
def quest(q):
    print(q)
    sys.stdout.flush()
    res = input()
    if res=="Vacant":
        exit()
        res = -1
    elif res=="Male":
        res = 1
    else:
        res = 0
    vals[q] = res
    return res

k = n//2
res1 = quest(0)
res2 = quest(k)

if (res2-res1)%2 != k%2:
    l = 0
    r = k
else:
    l = k
    r = n
    
while l<r+1:
    m = (l+r)//2
    res = quest(m)
    if (res-vals[l])%2 != (l-m)%2:
        r = m
    else:
        l = m
quest(l)
quest(r)
### BUGGY CODE ###

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

ans = 1
for a in A:
  ans *= a

if ans < 10**18 + 1:
  print (ans)
else:
  print (-1)

### FIXED CODE ###

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

if 0 in A:
  print (0)
  exit()
ans = 1
for a in A:
  ans *= a
  if ans > 10**18:
    print (-1)
    exit()
print (ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
d = dict()
count = 0
for el in a:
    temp = a.count(el)
    count += temp-1
    d[str(el)] = temp
count //= 2
for el in a:
    print(count - d[str(el)]+1)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
d = [0]*(n+1)
count = 0
for el, cnt in counter.most_common():
    d[el] = cnt
    count += cnt*(cnt-1)
count //= 2
for el in a:
    print(count - d[el] + 1)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
n1=n
s=0
for i in range(n-2):
    n1=n
    for j in range(i+1,n1-1):
        for k in range(j+1,n1):
            if a[j]+a[k]>a[i]:
                s+=1
            else:
                n1=k
                break
print(s)
            
        

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
l=len(a)
ans=0
for i in range(l-2):
    e=l-1
    for j in range(i+1,l-1):
        if e<=j:
            break
        while a[i]-a[j]>=a[e] and e>j:
            ans+=(e-j)
            e-=1
ans=(n*(n-1)*(n-2))//6-ans
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
m = 2
for i in li:
    if not isprime[i]:
        continue
    for k in li:
        if k%i == 0 and k!=i:
            isprime[k] = False
    m = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))


### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))
### BUGGY CODE ###

n = int(input())
a = list(input().split())
s = a[0]
for i in range(1,n):
  if (i+n)%2 == 0:
    s = s + " " + a[i]
  else:
    s = a[i] + " " + s
print(s)


  

### FIXED CODE ###

n = int(input())
a = list(input().split())
b = a[n-1::-2] + a[n%2::2]
print(' '.join(b))
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
ans = 0
for i in range(A,B+1):
    if i%C == 0:
        continue
    else:
        if i%D == 0:
            continue
        else:
            ans += 1
print(ans)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
print((B-A+1)-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//lcm(C,D)-(A-1)//lcm(C,D)))
### BUGGY CODE ###

from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
import math
import string
import fractions
import re
import array
import copy
import functools

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop

# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    n = int(input())
    l = list(map(int, input().split()))

    # eprint("=======================")
    while True:
        xx = min([x for x in l if x > 0])
        l = [(tt if tt==xx else tt%xx) for tt in l]

        # eprint(l)
        if all(x==l[0] for x in l):
            print(l[0])
            return 0
        if 1 in l:
            print(1)
            return 0
        if sum(l)==xx:
            print(xx)
            return 0
        # eprint("=======================")

    print(xx)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
import math
import string
import fractions
import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop

# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    n = int(input())
    l = list(map(int, input().split()))

    eprint("=======================")
    while True:
        xx = min([x for x in l if x > 0])
        # eprint("min_index: "+str(min_index))
        eprint("xx: "+str(xx))
        flag = 0
        for i in range(len(l)):
            if l[i] == xx and flag == 0:
                flag=1
            else:
                l[i] = l[i]%xx

        # eprint(l)
        if all(x==l[0] for x in l):
            # eprint(l)
            print(l[0])
            return 0
        if 1 in l:
            print(1)
            return 0
        if sum(l)==xx:
            print(xx)
            return 0
        eprint("=======================")

    print(xx)
    return 0


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


n=int(input())
a=[int(i) for i in input().split()]
a.sort()
i=1
while True:
    if len(a)<=1:
        break
    else:
        if i>=len(a):
            i=1
        if a[i] % a[0]==0:
            del a[i]
        else:
            a[i]-=a[0]
            if a[i]==0:
                del a[i]
    a.sort()
    i+=1
print(a[0])

### FIXED CODE ###


n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

for i in a:
    c=gcd(c,i)
print(c)
### BUGGY CODE ###

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

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

b = []
for i in range(n):
    b += [100 * (i + 1) for j in range(a[i][0])]
#print(b)

d = []
ans = 1000000000000000
for i in range(2 ** len(b)):
    check = 0
    c = []
    for j in range(len(b)):
        if (i >> j) & 1:
            c.append(b[j])
    for k in range(n):
        if c.count(100 * (k + 1)) == a[k][0]:
            check += a[k][1]
    #print(check)
    check += sum(c)
    if check >= m and len(c) < ans:
        ans = len(c)
    #print(ans, check, c)
    
    d.append(c)

print(ans)



### FIXED CODE ###

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

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

ans = 1000000000000000
for i in range(2 ** n):
    check = 0
    ac = 0
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            check += a[j][0] * 100 * (j + 1) + a[j][1]
            tmp += a[j][0]
        
        if check >= m:
            ans = min(ans, tmp)

        else:
            for k in reversed(range(n)):
                if not (i >> k) & 1:
                    ac = -(-(m - check) // ((k + 1) * 100))
                    if ac < a[k][0]:
                        ans = min(ans, ac + tmp)

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

def sum_digit(number: int):
    string = str(number)
    array = list(map(int, list(string)))
    return sum(array)


if __name__ == '__main__':
    number = int(input())

    sum_max = 0

    while number > 0:
        total_value = sum_digit(number)

        if total_value > sum_max:
            sum_max = total_value
        number -= 1
     
    print(sum_max)

### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


def get_most_significant_digit(number: int):
    separated_number = list(map(int, str(number)))
    return separated_number[0]


def count_digit(number: int):
    return len(str(number))


def generate_candidate_value(most_significant_digit, digit_count):
    filled_with_9 = 10 ** (digit_count - 1) - 1

    if digit_count > 1:
        candidate_value = str(most_significant_digit) + str(filled_with_9)
    else:
        candidate_value = str(most_significant_digit)
    return int(candidate_value)


def sum_digit(number: int, candidate_value: int):
    result = sum(list(map(int, str(candidate_value))))

    if number >= candidate_value:
        return result
    else:
        return result - 1


if __name__ == '__main__':
    number = int(input())

    # See: https://img.atcoder.jp/agc021/editorial.pdf
    most_significant_digit = get_most_significant_digit(number)
    digit_count = count_digit(number)
    candidate_value = generate_candidate_value(most_significant_digit,
                                               digit_count)

    result = sum_digit(number, candidate_value)
    print(result)
### BUGGY CODE ###

N = int(input())
C = [int(input()) for _ in range(5)]

P = [N, 0, 0, 0, 0, 0]
for time in range(1, 5 * N):
    for i in range(4, -1, -1):
        P[i+1] += min(C[i], P[i])
        P[i] -= min(C[i], P[i])
    if P[5] == N:
        print(time)
        break


### FIXED CODE ###

from math import ceil

N = int(input())
A = [int(input()) for _ in range(5)]

print(ceil(N / min(A)) + 4)
### BUGGY CODE ###

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

M = 0

for i in range(0,N-1):
  for j in range(i+1,N):
    M  += A[i] * A[j]
    if  M > 10**9 + 7:
      M = M %(10**9 +7)
print(M)


### FIXED CODE ###

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

M = 0
sum = 0
for i in range(N):
  sum += A[i]

for i in range(N-1):
  sum = sum - A[i]
  M += A[i] * sum
  if M > 10 ** 9 + 7:
    M = M % (10 ** 9 + 7)
print(M)
### BUGGY CODE ###

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

for i in range(1,n+1):
    if i != n+1:
        print('{} '.format(a.index(i)+1),end="")
    else:
        print(a.index(i)+1)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
dict = {}
for i in range(n):
    dict.setdefault(a[i],i+1)

for i in range(1,n+1):
    if i != n+1:
        print('{} '.format(dict[i]),end="")
    else:
        print(dict[i])
### BUGGY CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

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

for i in range(N):
        M = [A[i-1]]
        hoge = A[i]
        A[i] = A[i-1]
        for k in range(N):
                M.append(gcd(M[k],A[k]))

        if M[N] >= output:
                output = M[N]
        A[i]=hoge

print(output)

### FIXED CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

N = int(input())
A= list(map(int,input().split()))
output=0
KA=[0 for i in range(N)]
LA=[0 for i in range(N)]
GCD = []

for k in range(1,N):
        LA[k]=gcd(A[k-1],LA[k-1])

for k in range(1,N):
        KA[k]=gcd(A[N-k],KA[k-1])


for k in range(N):
        GCD.append(gcd(LA[k],KA[N-k-1]))
output = max(GCD)
print(output)
### BUGGY CODE ###

rflag = 0
s = input()
q = int(input())

for i in range(q):
    x = input().split()
    
    if (x[0] == '1'):
        rflag += 1
        # s = s[::-1]
    elif(x[0] == '2'):
        if((rflag % 2) == 0):
            rflag = 0
        else:
            s = s[::-1]
            rflag = 0
        
        if(x[1] == '1'):
            s = x[2] + s
        elif(x[1] == '2'):
            s += x[2]
if(rflag % 2 == 0):
    pass
else:
    s = s[::-1]

print(s)


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

import math
N = int(input())
a = list(map(int,input().split()))
for i in range(1,N+1):
    print(a.count(i))

### FIXED CODE ###

import math
N = int(input())
a = list(map(int,input().split()))
c = [0]*(N+1)
for i in range(N-1):
    b = a[i]
    c[b] += 1
for j in range(1,N+1):
    print(c[j])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

d = int(input())
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
T = [int(input()) - 1 for i in range(d)]
L = [[-1]]


def score(T):
    L = [-1 for j in range(26)]
    tmp = 0
    for i in range(d):
        tmp += S[i][T[i]]
        L[T[i]] = i
        tmp -= sum([C[j] * (i - L[j]) for j in range(26)])
    return tmp


m = int(input())
for k in range(m):
    p, q = map(int, input().split())
    T[p - 1] = q - 1
    print(score(T))


### FIXED CODE ###

d = int(input())
dd = d * (d + 1) // 2
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
T = [int(input()) - 1 for i in range(d)]
m = int(input())
PQ = [tuple(map(int, input().split())) for k in range(m)]
PQ = [(p - 1, q - 1) for p, q in PQ]

for p, q in PQ:
    T[p] = q
    L = [-1 for j in range(26)]
    X = [0 for j in range(26)]
    score = 0
    for i in range(d):
        score += S[i][T[i]]
        X[T[i]] += (d - i) * (i - L[T[i]])
        L[T[i]] = i
    for j in range(26):
        score -= C[j] * (dd - X[j])
    print(score)
### BUGGY CODE ###

import collections
import math


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


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total_ans = 0
for k, v in c.items():
    if v > 1:
        total_ans += combinations_count(v, 2)

for k_ball in A:
    if c[k_ball] > 2:
        print(
            total_ans
            - (combinations_count(c[k_ball], 2) - combinations_count(c[k_ball] - 1, 2))
        )
    elif c[k_ball] > 1:
        print(total_ans - 1)
    else:
        print(total_ans)

### FIXED CODE ###

# 解き直し
import collections

N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)

total = 0
for v in c.values():
    total += v * (v - 1) // 2

for k_ball in A:
    cnt = c[k_ball]
    print(total - (cnt * (cnt - 1) // 2) + ((cnt - 1) * (cnt - 2) // 2))
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
b = set(a)
cnt = 0
for i in b:
    if a.count(i)%2==1:
        cnt+=1
print(cnt)


### FIXED CODE ###

from collections import Counter
N = int(input())
a = [int(input()) for _ in range(N)]
ans = [i for i in Counter(a).values() if i%2==1]
print(len(ans))
### BUGGY CODE ###

num = int(input())

while True:
    for i in range(1,num+1):
        count =0
        for j in range(i):
             if i%(j+1) == 0:
                count +=1
    if count ==2:
        print(num)
        exit()
    else:
        num += 1

### FIXED CODE ###

num = int(input())

flag = False
while True:
    if num == 2:
        print(2)
        exit()
    for i in range(2, int(num**0.5)+1):
        if num % i ==0:
            flag = False
            break
        else:
            flag = True
    if flag:
        print(num)
        exit()
    else:
        num+=1
### BUGGY CODE ###

n, m = map(int, input().split())
cnt = {}
by = {}

for i in range(m):
  p, y = map(int, input().split())
  cnt[i] = [p, y]
  if p in by:
    s = by[p]
    s.append(y)
    s.sort()
    by[p] = s
  else:
    by[p] = [y]

for i in range(m):
  print(str(cnt[i][0]*1000000 + (list(by[cnt[i][0]]).index(cnt[i][1]))+1).zfill(12))

### FIXED CODE ###

n, m = map(int, input().split())
cnt = {}
y_p = {}
ans = [1 for i in range(n)]
y_ = []

for i in range(m):
  p, y = map(int, input().split())
  y_.append(y)
  cnt[i] = [p, y]
  y_p[y] = p
y_.sort()

for i in y_:
  p = y_p[i]
  y_p[i] = ans[p-1]
  ans[p-1] += 1

for i in range(m):
  p = cnt[i][0]
  y = cnt[i][1]
  print(str(p*1000000 + y_p[y]).zfill(12))
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    s = str(input())
    t = str(input())


    # 文字列S, Tのlongest common subsequenceを返す
    # なお、longest common substringではない
    # （要素同士がとなりあっていなくてもいい）ことに注意！
    def lcs(S, T):
        # 初期化
        dp = [[0] * (len(T) + 1) for j in range(len(S) + 1)]

        # dp[i][j]はS[:i]とT[:j]のlcsの長さを表す
        for i in range(len(S)):
            for j in range(len(T)):
                # その前までの値引き継ぎ
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
                # 望まれたニューカマーが来たら足す
                if S[i] == T[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

        # If you want to know just the length of the lcs, return dp[i + 1][j + 1].
        # Here we'll try to print the lcs.

        lcs_str = ''
        i, j = len(S)-1, len(T)-1
        while i >= 0 and j >= 0:
            if S[i] == T[j]:
                lcs_str += S[i]
                i -= 1
                j -= 1
            else:
                if dp[i][j+1] > dp[i+1][j]:
                    i -= 1
                else:
                    j -= 1

        return lcs_str[::-1]

    print(lcs(s, t))


resolve()

### FIXED CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    s = str(input())
    t = str(input())


    # 文字列S, Tのlongest common subsequenceを返す
    # なお、longest common substringではない
    # （要素同士がとなりあっていなくてもいい）ことに注意！
    def lcs(S, T):
        # 初期化
        dp = [[0] * (len(T) + 1) for j in range(len(S) + 1)]

        # dp[i][j]はS[:i]とT[:j]のlcsの長さを表す
        for i in range(len(S)):
            for j in range(len(T)):
                # その前までの値引き継ぎ
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
                # 望まれたニューカマーが来たら足す
                if S[i] == T[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

        # If you want to know just the length of the lcs, return dp[i + 1][j + 1].
        # Here we'll try to print the lcs.

        lcs_str = ''
        i, j = len(S)-1, len(T)-1
        while i >= 0 and j >= 0:
            if S[i] == T[j]:
                lcs_str += S[i]
                i -= 1
                j -= 1
            else:
                if dp[i][j+1] > dp[i+1][j]:
                    i -= 1
                else:
                    j -= 1

        return lcs_str[::-1]

    print(lcs(s, t))


resolve()
### BUGGY CODE ###

itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))


class Product:
    def __init__(self, price):
        self.price = price
        self.ticket = 0
        self.pay = price

    def getPay(self):
        return self.pay // 2 ** self.ticket


def highestProductIndex(products):
    highPrice = 0
    highPriceIndex = 0
    for index, product in enumerate(products):
        if highPrice < product.getPay():
            highPrice = product.getPay()
            highPriceIndex = index

    return highPriceIndex


products = []
for price in prices:
    products.append(Product(price))

for tickenNumber in range(ticketCount):
    index = highestProductIndex(products)
    products[index].ticket += 1

total = 0
for product in products:
    total += product.getPay()

print(total)

### FIXED CODE ###

import heapq


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))

h = []
for price in prices:
    _heappush_max(h, price)

for i in range(ticketCount):
    price = _heappop_max(h)
    _heappush_max(h, price // 2)
total = 0
for price in h:
    total += price

print(total)
### BUGGY CODE ###

N = int(input())
x, y = map(int, input().split())
for _ in range(N-1):
  n = 1
  a, b = map(int, input().split())
  while n*a < x or n*b < y:
    n += 1
  x, y = n*a, n*b
print(x+y)

### FIXED CODE ###

import math

N = int(input())
x, y = map(int, input().split())
for _ in range(N-1):
  a, b = map(int, input().split())
  # n = max(math.ceil(x/a), math.ceil(y/b))
  na = nb = 0
  if x%a == 0:
    na = x//a
  else:
    na = x//a+1
  if y%b == 0:
    nb = y//b
  else:
    nb = y//b+1
  n = max(na, nb)
  x, y = n*a, n*b
print(x+y)