import sys

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

# A = [0] * n

# B = [0] * n

# for i in range(n):

#     A[i], B[i] = map(int, input().split())

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

min_hp = h

max_hp = h + max(a for a, b in (AB))

 

dp = [sys.maxsize] * (max_hp + 1)

dp[0] = 0

 

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

    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))

    dp[i] = min(dp[i - a] + b for a, b in AB)

print((min(dp[h:])))
import sys

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

# A = [0] * n

# B = [0] * n

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

# for i in range(n):

#     A[i], B[i] = map(int, input().split())

min_hp = h

 

dp = [sys.maxsize] * (min_hp + 1)

dp[0] = 0

 

for i in range(0, min_hp + 1):

    for ab in AB: # type of spell

        next_index = min(i + ab[0], min_hp)

        dp[next_index] = min(dp[next_index], dp[i] + ab[1])

 

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]

# for i in range(n + 1):

#     for j in range(min(A[1:]) + 1):

#         dp[i][j] = min(B[1:])

#

# for i in range(1, n + 1):

#     for j in range(1, max_hp + 1):

#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])

#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])

print((dp[h]))
import sys

h, n = list(map(int, input().split()))
# A = [0] * n
# B = [0] * n
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))
dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0
for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print((min(dp[h:])))

import sys

h, n = list(map(int, input().split()))
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h
dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0
for i in range(0, min_hp + 1):
    for ab in AB:  # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])
# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print((dp[h]))

+AB = [list(map(int, input().split())) for _ in range(n)] -AB = [list(map(int, input().split())) for _ in range(n)] -max_hp = h + max(a for a, b in (AB)) -dp = [sys.maxsize] * (max_hp + 1) +dp = [sys.maxsize] * (min_hp + 1) -for i in range(1, max_hp + 1): -    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n)) -    dp[i] = min(dp[i - a] + b for a, b in AB) -print((min(dp[h:]))) +for i in range(0, min_hp + 1): +    for ab in AB:  # type of spell +        next_index = min(i + ab[0], min_hp) +        dp[next_index] = min(dp[next_index], dp[i] + ab[1]) +# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)] +# for i in range(n + 1): +#     for j in range(min(A[1:]) + 1): +#         dp[i][j] = min(B[1:]) +# +# for i in range(1, n + 1): +#     for j in range(1, max_hp + 1): +#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j]) +#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i]) +print((dp[h]))