import math

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





a = [0 for _ in range(n)]

b = [0 for _ in range(n)]

for i in range(n):

    a[i], b[i] = list(map(int,input().split()))



dp = []

for i in range(h + max(a)):

    dp.append(pow(2, 31) - 1)

dp[0] = 0



for i in range(1, len(dp)):

    '''

    tmp = dp[i]

    for j in range(n):

        tmp = min(tmp, dp[max(0, i-a[j])] + b[j])

    dp[i] = tmp

    '''

    dp[i] = min(dp[i - A] + B for A, B in zip(a, b))



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

inf = sys.maxsize



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

a = [0 for _ in range(n)]

b = [0 for _ in range(n)]

for i in range(n):

    a[i], b[i] = list(map(int,input().split()))



dp = [inf for _ in range(h + max([a[i] for i in range(n)]) + 10)] #dp[体力i削るのに必要な魔力]

dp[0] = 0



for i in range(1, len(dp)):

    for j in range(n):

        dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j])



#print(dp)

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

h, n = list(map(int, input().split()))
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
dp = []
for i in range(h + max(a)):
    dp.append(pow(2, 31) - 1)
dp[0] = 0
for i in range(1, len(dp)):
    """
    tmp = dp[i]
    for j in range(n):
        tmp = min(tmp, dp[max(0, i-a[j])] + b[j])
    dp[i] = tmp
    """
    dp[i] = min(dp[i - A] + B for A, B in zip(a, b))
print((min(dp[h:])))

import sys

inf = sys.maxsize
h, n = list(map(int, input().split()))
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
dp = [inf for _ in range(h + max([a[i] for i in range(n)]) + 10)]  # dp[体力i削るのに必要な魔力]
dp[0] = 0
for i in range(1, len(dp)):
    for j in range(n):
        dp[i] = min(dp[i], dp[max(0, i - a[j])] + b[j])
# print(dp)
print((min(dp[h:])))

-import math +import sys +inf = sys.maxsize -dp = [] -for i in range(h + max(a)): -    dp.append(pow(2, 31) - 1) +dp = [inf for _ in range(h + max([a[i] for i in range(n)]) + 10)]  # dp[体力i削るのに必要な魔力] -    """ -    tmp = dp[i] -        tmp = min(tmp, dp[max(0, i-a[j])] + b[j]) -    dp[i] = tmp -    """ -    dp[i] = min(dp[i - A] + B for A, B in zip(a, b)) +        dp[i] = min(dp[i], dp[max(0, i - a[j])] + b[j]) +# print(dp)