Harryxun/stf_run huggingface dataset:
N, A, B = map(int, input().split())

items = []
A_MAX = 0
B_MAX = 0
MAX_cost = 0
for _ in range(N):
    a, b, cost = map(int, input().split())
    items.append((a, b, cost))
    A_MAX += a
    B_MAX += b
    MAX_cost += cost

dp = [[float('infinity')] * (A_MAX + 1) for _ in range(B_MAX + 1)]

# dp[0][0] = 0
for a, b, cost in items:
    dp[b][a] = cost

for a, b, cost in items:
    for i in range(B_MAX + 1):
        for j in range(A_MAX + 1):
            if j - a > 0 and i - b > 0:
                dp[i][j] = min(dp[i][j], dp[i - b][j - a] + cost)

ans = float('infinity')
for k in range(B_MAX):
    for l in range(A_MAX):
        if dp[k][l] == float('infinity'):
            continue
        if A * dp[k] == dp[l] * B:
            ans = min(ans, dp[k][l])
if ans == float('infinity'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys



n, ma, mb = map(int, input().split())
abc = []

for _ in range(n):
    a, b, cost = map(int, input().split())
    abc.append((a, b, cost))

def main():
    sa = 0
    sb = 0
    for i in range(n):
        sa += abc[i][0]
        sb += abc[i][1]

    res = [[float('infinity')] * (sb + 1) for _ in range(sa + 1)]
    res[0][0] = 0

    for a, b, c in abc:

        for j in range(sa, -1, -1):
            for k in range(sb, -1, -1):
                if j >= a and k >= b:
                    res[j][k] = min(res[j][k], res[j-a][k-b] + c)

    ans = float('infinity')
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = min(ans, res[ma*i][mb*i])

    if ans == float('infinity'):
        return -1
    else:
        return ans

if __name__ == '__main__':
    ans = main()
    print(ans)
a,b,c = map(int,input().split())
if c-a-b<=0:
  print("No")
else:
  if (c-a-b)**2-4a*b>0:
    print("Yes")
  else("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
if c-a-b<=2:
  print("No")
else:
  if (c-a-b)**2-4*a*b>0:
    print("Yes")
  else:
    print("No")
n = int(input())
p = int(input())
if n <= 8 and p<= 8:
    print('Yay!')
else:
    print(':(')

### FIXED CODE ###

a, b = map(int, input().split())
if a<=8 and b<=8:
  print("Yay!")
else:
  print(":(")
A, B, C = map(int, input().split())
ans += A+B+C-min(A, min(B, C))
if (max(A, max(B, C)) + min(A, min(B, C))) % 2 != 0:
  ans += 1
  ans += (max(A, max(B, C))+1-min(A, min(B, C))) / 2
else:
  ans += (max(A, max(B, C))-min(A, min(B, C))) / 2
print(int(ans))

### FIXED CODE ###

A, B, C = map(int, input().split())
X = sorted([A, B, C])
ans = X[2]-X[1]
if (X[2]+X[0]+X[2]-X[1]) % 2 != 0:
    ans += 1
    ans += (X[2]+1-(X[0]+X[2]-X[1])) / 2
else:
    ans += (X[2]-(X[0]+X[2]-X[1])) / 2
print(int(ans))
import math
n=input()
s=input()

def f(b,n):
	if n<b:
		return n
	elif n>=b:
		return f(b, math.floor(n/b))+n%b

if s==n:
	print n+1
	quit()


# 2 <= b <= sqrt(n)
n_sqrt=int(math.sqrt(n))
for i in range(2, n_sqrt+1):
	if f(i,n)==s:
		print i
		quit()



# sqrt(n) < b <= n
# yakusuu
l=[]
for i in range(1, n_sqrt+1):
	if (n-s)%i==0:
		l.append(i)
		l.append((n-s)/i)


for i in l:
	b=i+1
	p=n/b
	q=n%b
	if p+q==s:
		print b
		quit()

print -1
	
	

### FIXED CODE ###

import math
n=input()
s=input()

def f(b,n):
	if n<b:
		return n
	elif n>=b:
		return f(b, math.floor(n/b))+n%b

if s==n:
	print n+1
	quit()


# 2 <= b <= sqrt(n)
n_sqrt=int(math.sqrt(n))
for i in range(2, n_sqrt+1):
	if f(i,n)==s:
		print i
		quit()



# sqrt(n) < b <= n
# yakusuu
l=[]
for i in range(1, n_sqrt+1):
	if (n-s)%i==0:
		l.append(i)
		l.append((n-s)/i)
l.sort()

for i in l:
	b=i+1
	if b**2<=n:
		continue
	p=n/b
	q=n%b
	if p+q==s:
		print b
		quit()

print -1
def main():
	# n,m = map(int,input().split())
	# n,k = map(int,input().split())
	# n = int(input())
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n)]
	# s = list(s)
	
	a = int(input())
	s = int(input())

	if a >= 3200:
		print("red")
	else:
		print(s)


 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	# n,m = map(int,input().split())
	# n,k = map(int,input().split())
	# n = int(input())
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n)]
	# s = list(s)
	
	a = int(input())
	s = str(input())

	if a >= 3200:
		print(s)
	else:
		print("red")


 
if __name__ == '__main__':
	main()
import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]

for _ in range(min(k,math.log(n, 10))):
    new_a = np.zeros(n)
    for j,l in enumerate(a):
        for i in range(-l,l+1):
            if j+i >= 0 and j+i<n:
                new_a[j+i]+=1
    a = new_a

print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))
from sys import stdin
N = int(stdin.readline().rstrip())
for _ in range(N):
    data.append([int(x) for x in stdin.readline().rstrip().split()])

ans = 0
for i in data:
    ans += (i[1] - i[0] + 1)
print(ans)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
data = []
for _ in range(N):
    data.append([int(x) for x in stdin.readline().rstrip().split()])

ans = 0
for i in data:
    ans += (i[1] - i[0] + 1)
print(ans)
import bisect
n,k = map(int, input().split( ))
x = list(map(int, input().split( )))

start = bisect.bisect_left(x,0)

if x[start] == 0:
    k -= 1
    n -= 1
    #x = x[:start] + [0] + x[start+1:]
else:
    x = x[:start] + [0] + x[start:]
#print(x)
ans = 10**15

for i in range(start,start + k - n ,-1):###
    tmp1 = -x[start-i]
    tmp2 = x[start+k-i]
    #print(tmp1,tmp2)
    ans = min(ans, tmp1*2 + tmp2, tmp1 + tmp2*2)

print(ans)


### FIXED CODE ###

##境界の処理が場当たり的すぎるが他を見てもコードの発想が理解できない
import bisect
n,k = map(int, input().split( ))
x = list(map(int, input().split( )))
inf = 10**15
x.append(inf)
start = bisect.bisect_left(x,0)

if x[start] == 0:
    k -= 1
    n -= 1
    x = [-inf]*k + x + [inf]*k###
else:
    x = [-inf]*k + x[:start] + [0] + x[start:] + [inf]*k###
#print(x)
ans = inf
start = bisect.bisect_left(x,0)
for i in range(k+1):###
    tmp1 = -x[start-i]
    tmp2 = x[start+k-i]
    #print(tmp1,tmp2)
    ans = min(ans, tmp1*2 + tmp2, tmp1 + tmp2*2)

print(ans)
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
      if (a>=b or abs(a-b)<1e-6) and rst>=(rsw**2-r**2)**.5: c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

### FIXED CODE ###

import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  st=[tx-sx,ty-sy]; rst=R(st)
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    F=[rwt<r,rsw<r]
    if F==[1,0] or F==[0,1]: return 0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos(round((sw[0]*st[0]+sw[1]*st[1])/rsw/rst,4))
      if C(a,b) and C(rst**2,rsw**2-r**2): return 0
  return 1

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]
import math
from collections import Counter
a, b = map(int, input().split())
n = math.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

### FIXED CODE ###

import fractions
import math
from collections import Counter
a, b = map(int, input().split())
n = fractions.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)
# ABC158 D
from collections import deque
s=input()
q=int(input())
l=[]

for i in range(q):
    l.append(list(map(str,input().split())))

cnt=0
front_str=''
end_str=''

t_str=deque(s)
front_str=deque(front_str)
end_str=deque(end_str)

for ll in l:
    if ll[0]=='1':
        cnt+=1
    elif ll[0]=='2':
        if cnt%2==0:
            if ll[1]=='1':
                front_str.appendleft(ll[2])
            elif ll[1]=='2':
                end_str.append(ll[2])
        elif cnt%2==1:
            if ll[1]=='1':
                end_str.appendleft(ll[2])
            elif ll[1]=='2':
                front_str.appendleft(ll[2])
ans=front_str+t_str+end_str
ans=list(ans)

if cnt%2==0:
    ans=''.join(ans)
else:
    ans=ans[::-1]
    ans=''.join(ans)
print(ans)



### FIXED CODE ###

# ABC158 D
from collections import deque
s=input()
q=int(input())
l=[]

for i in range(q):
    l.append(list(map(str,input().split())))

cnt=0
front_str=''
end_str=''

t_str=deque(s)
front_str=deque(front_str)
end_str=deque(end_str)

for ll in l:
    if ll[0]=='1':
        cnt+=1
    elif ll[0]=='2':
        if cnt%2==0:
            if ll[1]=='1':
                front_str.appendleft(ll[2])
            elif ll[1]=='2':
                end_str.append(ll[2])
        elif cnt%2==1:
            if ll[1]=='1':
                end_str.append(ll[2])
            elif ll[1]=='2':
                front_str.appendleft(ll[2])
ans=list(front_str)+list(t_str)+list(end_str)

if cnt%2==0:
    ans=''.join(ans)
else:
    ans=ans[::-1]
    ans=''.join(ans)
print(ans)
N, M = map(int, input().split())
dp = [int(input()) for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
dp = [0 for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
else:
    dp[1] = 0
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = 0
def search(x, y, t):
    if t > k:
        return x + y - 1
    elif x == n and y == m:
        return x + y
    elif x == n or a[x] > b[y]:
        return search(x, y + 1, t + b[y])
    elif y == m or a[x] < b[y]:
        return search(x + 1, y, t + a[x])
    return max(search(x + 1, y, t + a[x]), search(x, y + 1, t + b[y]))

ans = search(0, 0, t)
print(ans)


### FIXED CODE ###

import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0]
for i in range(n):
    sa.append(sa[-1] + a[i])
sb = [0]
for i in range(m):
    sb.append(sb[-1] + b[i])
ans = 0
for i, s in enumerate(sa):
    if s > k:
        break
    ans = max(ans, i + max(0, bisect.bisect_left(sb, k - s + 1) - 1))
print(ans)
s=split(input())
a=int(s[0])
b=int(s[1])
x=a*b
y=2*a+2*b
print(x,y)

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
print(a*b,2*a+2*b)
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(M):
  b = list(map(int, input().split()))
  B.append(b)
  
B.sort(reverse = True, key = lambda x : x[1])
A.sort()
count = 0

for x in B:
  i = x[0] - 1
  c = x[1]
  if A[count + i] > c:
    for j in range(i):
      if A[count + j] < c:
        A[count + j] = c
    break
  else:
    A[count:count + i + 1] = [c] * (i + 1)
    count += i + 1

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(M):
  b = list(map(int, input().split()))
  B.append(b)
  
B.sort(reverse = True, key = lambda x : x[1])
A.sort()
count = 0

for x in B:
  i = x[0] - 1
  c = x[1]
  if count + i >= N:
    if A[-1] > c:
      for j in range(count,N):
        if A[j] < c:
          A[j] = c
      break
    else:
      A[count:] = [c] * (N - count)
      break
    
  elif A[count + i] > c:
    for j in range(i):
      if A[count + j] < c:
        A[count + j] = c
    break
  else:
    A[count:count + i + 1] = [c] * (i + 1)
    count += i + 1

print(sum(A))
a = raw_input()
x,y = a.split(" ")
n = int(x)
m = int(y)
S = n*m
SUM = n * 2 + m * 2
print S + " " + SUM

### FIXED CODE ###

x = raw_input().split(" ")
 
a = int(x[0])
b = int(x[1])
 
print str(a*b) + " " + str(2*(a+b))
N = int(input())
A = list(map(int,input().split()))
A.sort()
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr
 
n = lcm_list(A)
F = factorization(n)
count = 0
for i,j in F:
  for k in range(j):
    i += i
    if i in A:
      count += 1

print(count)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split())) + [10**6+1]
A.sort()
B = np.zeros(10**6+1)
count = 0
for i in range(N):
  if B[A[i]] == 0:
    B[::A[i]] = 1
    if A[i] != A[i+1]:
      count += 1
print(count)
a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
b=input()
print(a[b])

### FIXED CODE ###

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
b=int(input())
print(a[b-1])
N,K=map(int, input().split()) 
R,S,P=map(int, input().split()) 
T=input()
SC=0

def point(w):
    if w=='r':
        return P
    elif w=='s':
        return R
    else:
        return S
    
Flag=[True for i in range(N)]

for i in range(N):
    SC+=point(T[i])
    if i+K<N and T[i]==T[i+K]:
        Flag[i+K]=False
return(SC)

### FIXED CODE ###

N,K=map(int, input().split()) 
R,S,P=map(int, input().split()) 
T=input()
SC=0

def point(w):
    if w=='r':
        return P
    elif w=='s':
        return R
    else:
        return S
    
Flag=[True for i in range(N)]

for i in range(N):
    if Flag[i]:
        SC+=point(T[i])
        if i+K<N and T[i]==T[i+K]:
            Flag[i+K]=False
print(SC)
N, M = map(int, input().split())
a = list(map(int, input().split()))

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

def lcm(a, b):
    return a * b // gcd(a, b)

f = lcm(a[0], a[1])
for i in range(2, N):
    f = lcm(f, a[i])

if 1 <= f//2 <= M:
    print((M-f//2)//f + 1)
else:
    print(0)

### FIXED CODE ###

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

def lcm(a, b):
    return a * b // gcd(a, b)

def div2(x):
    c = 0
    while x%2==0:
        x //= 2
        c+=1
    return c

def test():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(N):
        if a[i]%2 == 1:
            return 0
        a[i] //= 2

    t = div2(a[0])
    for i in range(N):
        if div2(a[i]) != t:
            return 0
        a[i] >>= t
    M >>= t

    L = a[0]
    for i in range(1, N):
        L = lcm(L, a[i])
        if L > M:
            return 0

    ans = (M-L)//(2*L)+1
    return ans

print(test())
n = (input())
a = int(n.split(" ")[0])
b = int(n.split(" ")[1])
lcm = int((a * b / math.gcd(a, b)))
print(lcm)

### FIXED CODE ###

import fractions

n = (input())
a = int(n.split(" ")[0])
b = int(n.split(" ")[1])
lcm = int((a * b / fractions.gcd(a, b)))
print(lcm)
n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)
def cmb(n,r,mod):
  p,q = 1,1
  r = min(r,n-r)
  for i in range(r):
    p = p*(n - i)%mod
    q = q*(i + 1)%mod
    Y = pow(q,10**9+5,mod)
  return p*Y%mod
ans = ans - cmb(n,a,mod) - cmb(n,b,mod) - 1
print(ans%mod)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)
def cmb(n,r,mod):
  if n == r:
    return 1
  p,q = 1,1
  r = min(r,n-r)
  for i in range(r):
    p = p*(n - i)%mod
    q = q*(i + 1)%mod
    Y = pow(q,10**9+5,mod)
  return p*Y%mod
ans = ans - cmb(n,a,mod) - cmb(n,b,mod) - 1
print(ans%mod)
n = int(input())
l = [i for i in range(1, n+1)
nl = []
    
for a in l:
     if a%15 != 0 or a%5 != 0 or a%3 != 0:
     	nl.append(a)
print(sum(nl))
  

### FIXED CODE ###

n = int(input())
l = [i for i in range(1, n + 1)]
nl = []

for a in l:
    if (a % 5 != 0) and (a % 3 != 0):
        nl.append(a)

print(sum(nl))
import numpy as np

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

ans = []

for i in range(H):
    tmp = list(map(str, input().rstrip()))
    if tmp.count("#")==0:
        continue
    else:
        ans.append(tmp)

ans = np.array(ans)

judge = []

for i in range(W):
    if np.where(ans[:, i]=="#")[0].shape[0]==0:
        judge.append(False)
    else:
        judge.append(True)

ans = ans[:, judge]

for i in range(ans.shape[0]):
    print("".join(ans[i]))

### FIXED CODE ###

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

a = []

# 必要な行だけ読み込む
for i in range(H):
    tmp = list(input())
    if "#" not in tmp:
        continue
    else:
        a.append(tmp)

# 転置して削って転置
a = list(zip(*a))
a = [x for x in a if "#" in x]
a = list(zip(*a))

for i in a:
    print("".join(i))
s = input()
s_num = int(s)
len_s = len(s)
list=[0 for x in range(len_s+1)]
for i in range(len_s-1,-1,-1):
    for j in range(1,9):
        if int(s[i:i+j])%2019==0:
            list[i]=list[i+j]+1
print(sum(list))
            

        

### FIXED CODE ###

s=list(input())
s.reverse()
s_len = len(s)

list = [0 for _ in range(2019)]
ans = 0
mod = 2019
li = [0]
digit = 0
for i in range(s_len):
    li.append((li[i] + int(s[i])*pow(10,digit,mod))%mod)
    digit+=1
for i in range(s_len+1):
    list[li[i]]+=1
for i in range(2019):
    x = list[i]
    ans += x*(x-1)/2
print(int(ans))
N, A, B = map(int,input().split())
S = input()

a_counter, b_counter = 0

while S != "":
  s = S[0]
  if s == "a" and a_counter + b_counter <=a+b:
    a_counter += 1
    print("Yes")
  elif s == "b" and b_counter <= b and a_counter + b_counter <=a+b:
    b_counter += 1
    print("Yes")
  else:
    print("No")
  
  S = S[1:]

### FIXED CODE ###

N, A, B = map(int,input().split())
S = input()

a_counter = 0
b_counter = 0

for i in range(N):
  s = S[0]
  if s == "a" and a_counter + b_counter <A+B:
    a_counter += 1
    print("Yes")
  elif s == "b" and b_counter < B and a_counter + b_counter <A+B:
    b_counter += 1
    print("Yes")
  else:
    print("No")
  
  S = S[1:]
x,a,b=map(int,input().split())
y=abs(x-a)
z=abs(b-x)
    if y<z:
        print('A')
    else:
        print('B')


### FIXED CODE ###

x,a,b=map(int,input().split())
y=abs(x-a)
z=abs(b-x)
if y<z:
    print('A')
else:
    print('B')
x = int(input())


while True:
	for i in range(2, x**0.5+1):
		if x%i==0:
			x += 1
			break

	print(x)
	break

	

### FIXED CODE ###

x = int(input())


while True:
	for i in range(2, int(x**0.5)+1):
		if x%i==0:
			x += 1
			break
	else:
		print(x)
		break
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if len(ans_neg) & 1 and not (ans_pos and ans_pos[-1] == 0):
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            if not pos or not ans_neg:
                drop_pos = True
            elif not neg or not ans_pos:
                drop_pos = False
            else:
                drop_pos = pos[-1] * ans_pos[-1] < neg[-1] * ans_neg[-1]

            if drop_pos:
                ans_neg.append(neg.pop())
                ans_pos.pop()
            else:
                ans_pos.append(pos.pop())
                ans_neg.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()
N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]

for X in range(10**N):
  X = str(X)
  
  #all　すべてがtrueならという意味
  if len(X) == N and all(X[s-1] == str(c) for s, c in SC):
    print(X[s-1])
    break
else:
  print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]
 
for X in range(10**N):
  X = str(X)
  
  #all　すべてがtrueならという意味
  if len(X) == N and all(X[s-1] == str(c) for s, c in SC):
    print(X)
    break
else:
  print(-1)
import math
 
num = [int(input()) for _ in range(5)]
num2 = [n if n % 10 == 0 else n - (n%10) + 10  for n in num]

c = []
for i, j  in enumerate(num):
    n = j
    for k,l in enumerate(num2):
        if  k == i:
            continue
        else:
            n += l
	c.append(n)
print(min(c))


### FIXED CODE ###

num = [int(input()) for _ in range(5)]
num2 = [n if n % 10 == 0 else n - (n%10) + 10  for n in num]

c = []
for i, j  in enumerate(num):
    n = j
    for k,l in enumerate(num2):
        if  k == i:
            continue
        else:
            n += l
    c.append(n)

print(int(min(c)))