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

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

mx=max(a for a,b in ab)

dp=[10**10]*(h+1+mx)

dp[0]=0

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

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

print((min(dp[h:])))
from functools import lru_cache

import sys

sys.setrecursionlimit(10 ** 8)

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

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

ab.sort(key=lambda abi:(abi[1]/abi[0],abi[0]))



@lru_cache(maxsize=None)

def dp(i):

  if i<=0:

    return 0

  else:

    ans=float('inf')

    for a,b in ab:

      val=b+dp(i-a)

      if val<ans:

        ans=val

      else:

        break

    return ans



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

from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)
h, n = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda abi: (abi[1] / abi[0], abi[0]))


@lru_cache(maxsize=None)
def dp(i):
    if i <= 0:
        return 0
    else:
        ans = float("inf")
        for a, b in ab:
            val = b + dp(i - a)
            if val < ans:
                ans = val
            else:
                break
        return ans


print((dp(h)))

+from functools import lru_cache +import sys + +sys.setrecursionlimit(10**8) -ab = [list(map(int, input().split())) for _ in range(n)] -mx = max(a for a, b in ab) -dp = [10**10] * (h + 1 + mx) -dp[0] = 0 -for i in range(1, h + 1 + mx): -    dp[i] = min(dp[i - a] + b for a, b in ab) -print((min(dp[h:]))) +ab = [tuple(map(int, input().split())) for _ in range(n)] +ab.sort(key=lambda abi: (abi[1] / abi[0], abi[0])) + + +@lru_cache(maxsize=None) +def dp(i): +    if i <= 0: +        return 0 +    else: +        ans = float("inf") +        for a, b in ab: +            val = b + dp(i - a) +            if val < ans: +                ans = val +            else: +                break +        return ans + + +print((dp(h)))