Harryxun/stf_run huggingface dataset:
from numba import njit


@njit(cache=True)
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()
n=int(input())
po,ne=[],[]
now=0
for i in range(n):
    p=0
    mp=0
    for j in input():
        p+=(1,-1)[j==")"]
        mp=min(p,mp)
    if mp:
        if p>=0:
            po.append((mp,p))
        else:ne.append((mp-p,-p))
    else:now+=p
po.sort(reverse=1)
ne.sort(reevrse=1)
for m,p in po+ne:
    if m+now<0:print("No");exit()
    else:now+=p
print("No") if now else print("Yes")

### FIXED CODE ###

n=int(input())
po,ne=[],[]
now=0
for i in range(n):
    p=0
    mp=0
    for j in input():
        p+=(1,-1)[j==")"]
        mp=min(p,mp)
    if mp:
        if p>=0:
            po.append((mp,p))
        else:ne.append((mp-p,-p))
    else:now+=p
po.sort(reverse=1)
ne.sort(reverse=1)
for m,p in po:
    if m+now<0:print("No");exit()
    else:now+=p
nnow=0
for m,p in ne:
    if m+nnow<0:print("No");exit()
    else:nnow+=p
print("Yes" if now==nnow else "No")
n, m = map(int, input().split())
# n: ketasuu
# m: num of list
data = [[0] * 2] * m
for i in range(m):
    a, b = map(int, input().split())
    # data[i][0], data[i][1] = a, b  >>>間違い
    data[i] = a, b
dataSort = sorted(data)
start = dataSort[0][0]
strVal = dataSort[0][1]

aList = ['1'] + ['0'] * (n - 1)

flag = True
for i in range(m):
    tar = dataSort[i][0]
    tarVal = dataSort[i][1]

    if (tar == 1 and tarVal == 0):
        # print('-1')
        ans = -1
        flag = False
        break
    if (tar == start):
        if (tarVal != strVal):
            ans = -1
            flag = False
            break

    else:
        start = tar
        strVal = tarVal

    aList[tar - 1] = str(tarVal)


if (flag == True):
    ans = ''.join(aList)

print(ans)


### FIXED CODE ###

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

temp = list(['?'] * n)

# print(temp)
if (m == 0):
    if (n == 1):
        ans = 0
    else:
        ans = '1' + '0' * (n - 1)

else:
    for _ in range(m):
        s, c = map(int, input().split())
        if (s == 1 and c == 0 and n >= 2):
            print(-1)
            exit()
        else:
            pass

        if (temp[s-1] == '?'):
            temp[s - 1] = str(c)
        elif (temp[s - 1] == str(c)):
            pass
        else:
            print(-1)
            exit()

    if (temp[0] == '?'):
        temp[0] = '1'

    ans01 = ''.join(temp)
    ans = ans01.replace('?', '0')

print(ans)
arr = input().split(" ")
N = int(arr[0])
K = int(arr[1])

HP_arr = input().split(" ")
HP_arr.sort(reverse=True)
HP_arr = [int(i) for i in HP_arr ]

while(True):
    if(K > 0):
        HP_arr.pop(0)
        K -= 1
    else:
        break

print(sum(HP_arr))

### FIXED CODE ###

arr = input().split(" ")
H = int(arr[0])
K = int(arr[1])

HPs = input().split(" ")
HPs = [int(i) for i in HPs ]
HPs.sort(reverse=True)

if(K == 0):
    print(sum(HPs))
else:
    print(sum(HPs[K:]))
X,Y,A,B,C = map(int,input().split())
P = [int(i) for i in input().split()]
Q = [int(i) for i in input().split()]
R = [int(i) for i in input().split()]
from collections import deque
P_sort = sorted(P,reverse=True)[0:X]
Q_sort = sorted(Q,reverse=True)[0:Y]
R_sort = deque(sorted(R,reverse=True)[0:X+Y])
PQ = sorted(P_sort + Q_sort)
for i in range(len(PQ)):
    if R_sort[0] > PQ[i]:
        r = R_sort.popleft
        PQ[i] = r
print(sum(PQ))

### FIXED CODE ###

X,Y,A,B,C = map(int,input().split())
P = [int(i) for i in input().split()]
Q = [int(i) for i in input().split()]
R = [int(i) for i in input().split()]
from collections import deque
P_sort = sorted(P,reverse=True)[0:X]
Q_sort = sorted(Q,reverse=True)[0:Y]
R_sort = deque(sorted(R,reverse=True)[0:X+Y])
PQ = sorted(P_sort + Q_sort)
for i in range(len(PQ)):
    if R_sort[0] > PQ[i]:
        r = R_sort.popleft()
        PQ[i] = r
    if not R_sort:
      break
print(sum(PQ))
N,M=map(int,input().split())

li=list(range(N+1))
count=0

#print(li)
for i in range(M,N+2):
    small=(i*(i-1))//2
    large=small+li[-i]*i
    count+=large-small+1

print(count%(pow(10,9)+7))

### FIXED CODE ###

S=input()

N=len(S)
count=0
tot=[0]*2019
S=S[::-1]
base=0
#print(S)
for i,s in enumerate(S):
    base+=int(s)*pow(10,i,2019)
    base%=2019
    #tot[base]+=1
    #print(base)
    if base==0:
        count+=1
    count+=tot[base]
    #print(tot[base],i,base)
    tot[base]+=1
#print(tot)    

print(count)
n,m=map(int,input().split())
x=[[] for _ in range(n+1)]
ans=[False]*(n+1)
for i in range(m):
    p,y=map(int,input().split())
    x[p].append([y,i])

for p in range(1,n+1):
    x[p].sort()
    for j in range(len(x[p])):
        ans[x[p][j][1]]=str(p).zfill(6)+str(j+1).zfill(6)

for i in range(n+1):
    print(ans[i])

### FIXED CODE ###

N,M=map(int,input().split())
a=[[i]+list(map(int,input().split())) for i in range(M)]
a.sort(key=lambda x:(x[1],x[2]))

j=0
for i in range(M):
    if j!=a[i][1]:
        j=a[i][1]
        k=1
    s=format(a[i][1],'0>6') + format(k,'0>6')
    a[i].append(s)
    k+=1

a.sort()
for i in range(M):
    print(a[i][3])
import sys

def main():

	p = 0

	args = sys.argv
	n = int(args[1])
	for i in range(1, n):
		if i % 2 == 1:
			p = p + 1
	
	print(p/n)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():

	p = 0

	args = sys.argv
	n = int(input())
	
	print((int(n/2) + n%2 )/n)

if __name__ == "__main__":
    main()
from collections import defaultdict
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

N = getN()
nums = getList()
dup = defaultdict(int)

for n in nums:
    dup[n] += 1

poss = len(dup.keys())
dupdup = 0
for val in dup.values():
    if val % 2 == 0:
        dupdup += 1

if dupdup % 2 == 0:
    print(poss)
else:
    print(poss-1)

### FIXED CODE ###

from collections import defaultdict
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

N = getN()
nums = getList()
dup = defaultdict(int)

for n in nums:
    dup[n] += 1

poss = len(dup.keys())
dupdup = 0
for val in dup.values():
    if val % 2 == 0:
        dupdup += 1

if dupdup % 2 == 0:
    print(poss)
else:
    print(poss-1)
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
que = deque([])
que.append(A.popleft())
while A:
    if turn == 1:
        a = A.pop()
        if abs(a-que[0])<=abs(a-que[-1]):
            que.append(a)
        else:
            que.appendleft(a)
        if A:
            a = A.pop()
            if abs(a-que[0])<=abs(a-que[-1]):
                que.append(a)
            else:
                que.appendleft(a)
    else:
        a = A.popleft()
        if abs(a-que[0])<=abs(a-que[-1]):
            que.append(a)
        else:
            que.appendleft(a)
        if A:
            a = A.popleft()
            if abs(a-que[0])<=abs(a-que[-1]):
                que.append(a)
            else:
                que.appendleft(a)
    turn = 1-turn
cnt = 0
for i in range(1,N):
    cnt += abs(que[i]-que[i-1])
print(cnt)

### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
B = deque([])
B.append(A.popleft())
cnt = 0
while A:
    a0 = A[0]
    a1 = A[-1]
    b0 = B[0]
    b1 = B[-1]
    c00 = abs(a0-b0)
    c01 = abs(a0-b1)
    c10 = abs(a1-b0)
    c11 = abs(a1-b1)
    cmax = max(c00,c01,c10,c11)
    if cmax == c00:
        B.appendleft(A.popleft())
    elif cmax == c01:
        B.append(A.popleft())
    elif cmax == c10:
        B.appendleft(A.pop())
    else:
        B.append(A.pop())
    cnt += cmax
print(cnt)
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
dis = []
ans = 0
for i in range(m-1):
    dis.append(x[i+1]-x[i])
    ans += x[i+1]-x[i]
dis.sort(reverse = True)
for j in range(n-1):
    ans -= dis[j]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
dis = []
ans = 0
if n>m:
  print(0)
  exit()
for i in range(m-1):
    dis.append(x[i+1]-x[i])
    ans += x[i+1]-x[i]
dis.sort(reverse = True)
for j in range(n-1):
    ans -= dis[j]
print(ans)
a,b = map(int,(input().split()))

count = 1
while True:
    if count ==1:
        temp = a * count 
    else:
        temp = a + ((a-1) * (count -1))
    if temp >= b:
        print(count)
        exit()
    else:
        count += 1

### FIXED CODE ###

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

count = 0
temp = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        temp += 1
    else:
        temp = 0
    count = max(count,temp)
print(count)
n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

for i in range(1,n):
    
    for j in range(0,n):
        print(sort_list[j])
        if j is not n - 1:
            print(" ")
        else:
            print("\n")
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[j] > v:
        sort_list[j+1] = sort_list[j]
        j = j - 1
    sort_list[j+1] = v




### FIXED CODE ###

import sys

n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

for i in range(0,n):
    
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[j] > tmp:
        sort_list[j+1] = sort_list[j]
        j = j - 1

    sort_list[j+1] = tmp


    for k in range(0,n):
        sys.stdout.write(str(sort_list[k]))
        if k is not n - 1:
            sys.stdout.write(" ")
        elif i is not n - 1:
            sys.stdout.write("\n")
            
print("")
input(x)
x ** 3

### FIXED CODE ###

x = int(input())
print(x ** 3)
s=input()
i=1
while 1:
    if s[i-1]!="1":
        t=i 
        ans=s[i-1]
        break
    i+=1
# print(t)
if int(input())<=t:
    print(1);exit()
print(ans)

### FIXED CODE ###

s=input()
i=1
while 1:
    if i==len(s)+1:
        print(1);exit()
    if s[i-1]!="1":
        t=i 
        ans=int(s[i-1])
        break
    i+=1
# print(t)
if int(input())<t:
    print(1);exit()
print(ans)
a,b =map(int,input.split())
print(":(" if a>8 or b>8 else "Yay!")

### FIXED CODE ###

a,b =map(int,input().split())
print(":(" if a>8 or b>8 else "Yay!")
import numpy as np
array = np.zeros((3, 3), dtype="int8")
for i in range(3):
    inputs = map(int, input().split())
    for j in range(3):
        array[i, j] = inputs[j]
    
b_1 = array[0, 0]
b_2 = array[0, 1]
b_3 = array[0, 2]
a_2 = array[1, 0] - b_1
a_3 = array[2, 0] - b_1
if (array[1, 1] == (a_2 + b_2)) & (array[2, 2] == (a_3 + b_3)):
    flag = 1
else:
    flag = 0

if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

l = [[] for _ in range(3)]
for i in range(0, 3):
    l[i] = [int(_) for _ in input().split()]
t = [0, 0, 0]
for i in range(0, 3):
    for j in range(0, 3):
        t[i] += l[j][i]
p = (t[0] - t[1]) / 3
q = (t[0] - t[2]) / 3
if l[0][0]-p == l[0][1] and l[0][0]-q == l[0][2] and l[1][0]-p == l[1][1] and l[1][0]-q == l[1][2] and l[2][0]-p == l[2][1] and l[2][0]-q == l[2][2]:
    print('Yes')
else:
    print('No')
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()




### FIXED CODE ###

m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if n >= m[a] and dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'
    cell_list = list()

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W, cell_list)
    print(answer)


def resolve(q, S, D, H, W, cell_list):
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W, cell_list)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    V=LI()
    
    ans=0
    import heapq
    
    #左からa個，右からb個とって，あまり分で負数を捨てる
    for a in range(K+1):
        for b in range(K+1):
            if a+b>K:
                break
            hq=[]
            heapq.heapify(hq)
            for i in range(a):
                heapq.heappush(hq,V[i])
            for j in range(b):
                heapq.heappush(hq,V[N-1-j])
                
            temp=0
            rem=K-(a+b)
            for i in range(a+b):
                v=heapq.heappop(hq)
                if v>=0:
                    temp+=v
                else:
                    if rem>0:
                        rem-=1
                    else:
                        temp+=v
                        
            ans=max(ans,temp)
            
    print(ans)
                
            

main()


### FIXED CODE ###

#import heapq
import copy

N,K=map(int,input().split())
V=list(map(int,input().split()))
V.append(0)#右から取る時用

S=[0]*(N+1)#累積和
for i in range(N):
    S[i+1]=S[i]+V[i]

#左からi番目まで見たときに，持っている負の宝石
left=[[] for _ in range(N+1)]
for i in range(N):
    left[i+1]=copy.deepcopy(left[i])
    if V[i]<0:
        left[i+1].append(V[i])
        left[i+1].sort()
       
        
ans=0
#左からi個，右からj個とったときについて考える
for i in range(N+1):
    temp=S[i]
    rem=copy.deepcopy(left[i])
    #heapq.heapify(rem)
    for j in range(N+1-i):
        if i+j>K:
            break
        temp+=S[-1]-S[N-j]
        if V[N-j]<0:
            #heapq.heappush(rem,V[N-j])
            rem.append(V[N-j])
            rem.sort()
        ret=K-(i+j)#負の宝石を返却できる回数
        if ret>0:
            for k in range(min(ret,len(rem))):
                temp-=rem[k]
        ans=max(ans,temp)
        temp=S[i]
        
print(ans)
R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print(N*(N-1)//2)
    exit()







count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)



### FIXED CODE ###



R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)
import sys
S = include()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == b:
        print(a)
else:
    sys.exit()
sys.e

### FIXED CODE ###

import sys
S = input()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == c:
        print(a)
else:
    sys.exit()
sys.exit()
a=input()
b=input()
if(0<=a<=9 and 0<=b<=9):
  print(a*b)
else:
  print(-1)
  

### FIXED CODE ###


a,b = list(map(int, input().split()))
  
if(1<=a<=9 and 1<=b<=9):
    print(a*b)

else:
    print(-1)
A=list(map(int,input.split()))
if A[0]+A[1]+A[2]>=22:
  print("bust")
else:
  print("win")

### FIXED CODE ###

A=list(map(int,input().split()))
if A[0]+A[1]+A[2]>=22:
  print("bust")
else:
  print("win")
H, A = map(int, input.split())
i = 0
while H <= 0:
  H -= A
  i += 1
print(i)

### FIXED CODE ###

H, A = map(int, input().split())
i = 0
while H > 0:
  H -= A
  i += 1
print(i)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
'''
with open('./b20.txt') as f:
    N, M, K = map(int, f.readline().split())
    A = list(map(int, f.readline().split()))
    B = list(map(int, f.readline().split()))
'''

A_cnt = 0
B_cnt = 0
ans = 0
nowK = K
for A_idx in range(N):
    if nowK < A[A_idx]:
        break
    ans += 1
    nowK -= A[A_idx]
    A_cnt += 1
for B_idx in range(M):
    if nowK < B[B_idx]:
        break
    ans += 1
    nowK -= B[B_idx]
    B_cnt += 1
tmp_ans = ans
finish = False
for i in range(A_cnt, 0, -1):
    nowK += A[i]
    tmp_ans -= 1
    for j in range(B_cnt, M):
        if finish or nowK < B[j]:
            break
        nowK -= B[j]
        tmp_ans += 1
        if j == M - 1:
            finish = True
    B_idx = j
    ans = max(tmp_ans, ans)
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()))
ans = 0
A_cumulative_sum = [0]
B_cumulative_sum = [B[0]]
for i in range(N):
    A_cumulative_sum.append(A[i] + A_cumulative_sum[i])
for i in range(1, M):
    B_cumulative_sum.append(B[i] + B_cumulative_sum[i - 1])

for i in range(N + 1):
    if K < A_cumulative_sum[i]:
        remaining_time = K
        idx = bisect.bisect_right(B_cumulative_sum, remaining_time)
        ans = max(ans, idx)
        break
    else:
        remaining_time = K - A_cumulative_sum[i]
        idx = bisect.bisect_right(B_cumulative_sum, remaining_time)
        ans = max(ans, i + idx)
print(ans)

# 113897
from itertools import product
from math import ceil


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue

        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        tmp = ceil((g - sums) / indices[-1])
        if tmp < p[indices[-1]]:
            ans = min(ans, counts + tmp)
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

from itertools import product


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue
        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        for i in range(1, p[indices[-1]-1]):
            if sums + indices[-1] * i >= g:
                ans = min(ans, counts + i)
                break
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))
n=int(input())
a=[int(input()) for _ in range(n)]
p=a[::]
m=max(a)
a.delete(m)
m2=max(a)
for i in p:
  if i==m:
    print(m2)
  else:
    print(m)

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
p=a[::]
m=max(a)
a.remove(m)
m2=max(a)
for i in p:
  if i==m:
    print(m2)
  else:
    print(m)
b = input()

a = ['A', 'C', 'G', 'T']
for i in range(len()):
  if a[i] == b:
    print(a[i])
    break

### FIXED CODE ###

b = input()

a = {'A':'T', 'C':'G', 'G':'C', 'T':'A'}

print(a[b])
H,W = map(int,input().split())
ans = []
for i in range(W):
    ans.append(input())
for j in ans:
    print(j)
    print(j)

### FIXED CODE ###

H,W = map(int,input().split())
ans = []
for i in range(H):
    ans.append(input())
for j in ans:
    print(j)
    print(j)
H,N=map(int, input().split())
import math



MAX=10**4+1
def solve(r,idx):
  if idx==N:
    return MAX
  if r%A[idx][1]==0:
    return (r//A[idx][1])*A[idx][2]
  else:
    return min((r//A[idx][1]+1)*A[idx][2],(r//A[idx][1])*A[idx][2]+solve(r%A[idx][1],idx+1))

def main():
  A=[]
  B=[]
  for i in range(N):
    a,b=map(int, input().split())
    A.append([a/b,a,b])
  if N==1:
    if H%A[0][1]==0:
    	print((H//A[0][1])*A[0][2])
  	else:
    	print((H//A[0][1]+1)*A[0][2])
    return
  A=sorted(A)[::-1]

  if H%A[0][1]==0:
    print((H//A[0][1])*A[0][2])
  else:
    ans=min((H//A[0][1]+1)*A[0][2],(H//A[0][1])*A[0][2]+solve(H%A[0][1],1))
    print(ans)

main()

### FIXED CODE ###

H,N=map(int, input().split())
A=[]
B=[]

dp=[10**10]*(H+1)
dp[0]=0
for n in range(N):
  a,b=map(int, input().split())
  A.append(a)
  B.append(b)
    
for h in range(1,H+1):
  for n in range(N):
    if h-A[n]>=0:
      dp[h]=min(dp[h],dp[h-A[n]]+B[n])
    else:
      dp[h]=min(dp[h],B[n])
print(dp[H])