INF = 10 ** 18





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

AB = [list(map(int, input().split())) for _ in range(N)]



dp = [[INF] * (H + 1) for _ in range(N + 1)]

dp[0][0] = 0

for i in range(N):

    for j in range(H + 1):

        if j < AB[i][0]:

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

        else:

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

    

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



# for d in dp:

#     print (d)
import sys

input = sys.stdin.readline



INF = 10 ** 18



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



dp = [INF] * (H + 1)

dp[0] = 0



for i in range(N):

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

    for j in range(H + 1):

        if j < A:

            dp[j] = min(dp[j], dp[0] + B)

        else:

            dp[j] = min(dp[j], dp[j - A] + B)

    

print((dp[H]))



# for d in dp:

#     print (d)
INF = 10**18
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
print((dp[N][H]))
# for d in dp:
#     print (d)

import sys

input = sys.stdin.readline
INF = 10**18
H, N = list(map(int, input().split()))
dp = [INF] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = list(map(int, input().split()))
    for j in range(H + 1):
        if j < A:
            dp[j] = min(dp[j], dp[0] + B)
        else:
            dp[j] = min(dp[j], dp[j - A] + B)
print((dp[H]))
# for d in dp:
#     print (d)

+import sys + +input = sys.stdin.readline -AB = [list(map(int, input().split())) for _ in range(N)] -dp = [[INF] * (H + 1) for _ in range(N + 1)] -dp[0][0] = 0 +dp = [INF] * (H + 1) +dp[0] = 0 +    A, B = list(map(int, input().split())) -        if j < AB[i][0]: -            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1]) +        if j < A: +            dp[j] = min(dp[j], dp[0] + B) -            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1]) -print((dp[N][H])) +            dp[j] = min(dp[j], dp[j - A] + B) +print((dp[H]))