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

skills = []

for _ in range(n):

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

  skills.append((a,b))

dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]

dp[0] = 0

  

for i in range(len(dp)):

  if dp[i] ==float('inf'):

    continue

  for damage,mp in skills:

    if i+damage >= len(dp):

      continue

    if dp[i+damage] > dp[i] + mp:

      dp[i+damage] = dp[i]+mp

ans = min([x for x in dp[h:] if x>0])

print(ans)

#print(dp)



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

magic = []

maxa = 0

for _ in range(n):

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

  maxa = max(maxa,a)

  magic.append((a,b))

#magic.sort()



dp = [float('inf') for _ in range(h + maxa)]

dp[0] = 0



for i in range(h):

  for a,b in magic:

    if i+a > h+maxa:

      continue

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

print((min(dp[h:])))
h, n = list(map(int, input().split()))
skills = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    skills.append((a, b))
dp = [float("inf") for _ in range(h + max(skills, key=lambda x: x[1])[1] + 1)]
dp[0] = 0
for i in range(len(dp)):
    if dp[i] == float("inf"):
        continue
    for damage, mp in skills:
        if i + damage >= len(dp):
            continue
        if dp[i + damage] > dp[i] + mp:
            dp[i + damage] = dp[i] + mp
ans = min([x for x in dp[h:] if x > 0])
print(ans)
# print(dp)

h, n = list(map(int, input().split()))
magic = []
maxa = 0
for _ in range(n):
    a, b = list(map(int, input().split()))
    maxa = max(maxa, a)
    magic.append((a, b))
# magic.sort()
dp = [float("inf") for _ in range(h + maxa)]
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + maxa:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])
print((min(dp[h:])))

-skills = [] +magic = [] +maxa = 0 -    skills.append((a, b)) -dp = [float("inf") for _ in range(h + max(skills, key=lambda x: x[1])[1] + 1)] +    maxa = max(maxa, a) +    magic.append((a, b)) +# magic.sort() +dp = [float("inf") for _ in range(h + maxa)] -for i in range(len(dp)): -    if dp[i] == float("inf"): -        continue -    for damage, mp in skills: -        if i + damage >= len(dp): +for i in range(h): +    for a, b in magic: +        if i + a > h + maxa: -        if dp[i + damage] > dp[i] + mp: -            dp[i + damage] = dp[i] + mp -ans = min([x for x in dp[h:] if x > 0]) -print(ans) -# print(dp) +        dp[i + a] = min(dp[i] + b, dp[i + a]) +print((min(dp[h:])))