# coding: utf-8

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

AB=[[0,0]]

for i in range(N):

    AB.append(list(map(int,input().split())))



INF=10**9



dp=[[INF for i in range(H+1)] for j in range(N+1)]



for i in range(N+1):

    dp[i][0]=0





for i in range(1,N+1):

    for j in range(1,H+1):

        dp[i][j]=min(dp[i-1][j],dp[i][max(j-AB[i][0],0)] + AB[i][1])

        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])

        





print((dp[N][H]))

# coding: utf-8

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

AB=[[0,0]]

for i in range(N):

    AB.append(list(map(int,input().split())))

 

INF=10**9



dp=[INF for i in range(H+1)]

dp[0]=0



for i in range(1,N+1):

    for j in range(1,H+1):

        dp[j]=min(dp[j],dp[max(0,j-AB[i][0])] + AB[i][1])



print((dp[H]))
# coding: utf-8
H, N = list(map(int, input().split()))
AB = [[0, 0]]
for i in range(N):
    AB.append(list(map(int, input().split())))
INF = 10**9
dp = [[INF for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    for j in range(1, H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - AB[i][0], 0)] + AB[i][1])
        # print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
print((dp[N][H]))

# coding: utf-8
H, N = list(map(int, input().split()))
AB = [[0, 0]]
for i in range(N):
    AB.append(list(map(int, input().split())))
INF = 10**9
dp = [INF for i in range(H + 1)]
dp[0] = 0
for i in range(1, N + 1):
    for j in range(1, H + 1):
        dp[j] = min(dp[j], dp[max(0, j - AB[i][0])] + AB[i][1])
print((dp[H]))

-dp = [[INF for i in range(H + 1)] for j in range(N + 1)] -for i in range(N + 1): -    dp[i][0] = 0 +dp = [INF for i in range(H + 1)] +dp[0] = 0 -        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - AB[i][0], 0)] + AB[i][1]) -        # print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1]) -print((dp[N][H])) +        dp[j] = min(dp[j], dp[max(0, j - AB[i][0])] + AB[i][1]) +print((dp[H]))