# 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-1][max(j-AB[i][0],0)] + AB[i][1],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)] 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)] 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 - 1][max(j - AB[i][0], 0)] + AB[i][1],
            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)] 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]))

-        dp[i][j] = min( -            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], -        ) +        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - AB[i][0], 0)] + AB[i][1])