import sys



input = sys.stdin.readline

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

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



max_damage = max(damage for damage, cost in magic)

dp = [0] * (H + max_damage)



for x in range(1, H + max_damage):

    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)



ans = min(dp[H:])



print(ans)

import sys



input = sys.stdin.readline

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

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



dp = [0] * (H + 1)



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

    dp[i] = min(dp[max(i - damage, 0)] + cost for damage, cost in magic)



ans = dp[H]



print(ans)

import sys

input = sys.stdin.readline
H, N = list(map(int, input().split()))
magic = [list(map(int, input().split())) for _ in range(N)]
max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)
for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)
ans = min(dp[H:])
print(ans)

import sys

input = sys.stdin.readline
H, N = list(map(int, input().split()))
magic = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (H + 1)
for i in range(1, H + 1):
    dp[i] = min(dp[max(i - damage, 0)] + cost for damage, cost in magic)
ans = dp[H]
print(ans)

-max_damage = max(damage for damage, cost in magic) -dp = [0] * (H + max_damage) -for x in range(1, H + max_damage): -    dp[x] = min(dp[x - damage] + cost for damage, cost in magic) -ans = min(dp[H:]) +dp = [0] * (H + 1) +for i in range(1, H + 1): +    dp[i] = min(dp[max(i - damage, 0)] + cost for damage, cost in magic) +ans = dp[H]