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



f_inf = float("inf")

dp = [f_inf] * (h + 1)

dp[0] = 0

for i in range(n):

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

    for j in range(h):

        next_j = min(j + a, h)

        dp[next_j] = min(dp[next_j], dp[j] + b)



print((dp[h]))
import sys



sys.setrecursionlimit(10 ** 7)

f_inf = float('inf')

mod = 10 ** 9 + 7





def resolve():

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

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



    dp = [f_inf] * (h + 1)

    dp[0] = 0

    for a, b in AB:

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

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



    print((dp[h]))





if __name__ == '__main__':

    resolve()

h, n = list(map(int, input().split()))
f_inf = float("inf")
dp = [f_inf] * (h + 1)
dp[0] = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(h):
        next_j = min(j + a, h)
        dp[next_j] = min(dp[next_j], dp[j] + b)
print((dp[h]))

import sys

sys.setrecursionlimit(10**7)
f_inf = float("inf")
mod = 10**9 + 7


def resolve():
    h, n = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(n)]
    dp = [f_inf] * (h + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(1, h + 1):
            dp[i] = min(dp[i], dp[max(0, i - a)] + b)
    print((dp[h]))


if __name__ == "__main__":
    resolve()

-h, n = list(map(int, input().split())) +import sys + +sys.setrecursionlimit(10**7) -dp = [f_inf] * (h + 1) -dp[0] = 0 -for i in range(n): -    a, b = list(map(int, input().split())) -    for j in range(h): -        next_j = min(j + a, h) -        dp[next_j] = min(dp[next_j], dp[j] + b) -print((dp[h])) +mod = 10**9 + 7 + + +def resolve(): +    h, n = list(map(int, input().split())) +    AB = [list(map(int, input().split())) for _ in range(n)] +    dp = [f_inf] * (h + 1) +    dp[0] = 0 +    for a, b in AB: +        for i in range(1, h + 1): +            dp[i] = min(dp[i], dp[max(0, i - a)] + b) +    print((dp[h])) + + +if __name__ == "__main__": +    resolve()