import sys

import numpy as np



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

ab = np.array(sys.stdin.read().split(), dtype=np.int64)

aaa = ab[0::2]

bbb = ab[1::2]



dp = np.zeros(10001, dtype=np.int64)

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

    dp[i] = (dp[i - aaa] + bbb).min()

print((dp[h]))





# https://atcoder.jp/contests/abc153/submissions/9776226

# coding=utf-8

# Date: 2020-01-08

# Author: lee215



get = lambda: int(input().strip())

getl = lambda: input().strip()

gets = lambda: list(map(int, input().strip().split()))

getss = lambda n: [gets() for _ in range(n)]



h, N = gets()

AB = getss(N)



dp = [0] + [float('inf')] * h

for a, b in AB:

    for i in range(h):

        j = min(i + a, h)

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

print((dp[h]))
import sys
import numpy as np

h, n = list(map(int, input().split()))
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]
dp = np.zeros(10001, dtype=np.int64)
for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print((dp[h]))
# https://atcoder.jp/contests/abc153/submissions/9776226

# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(input().strip())
getl = lambda: input().strip()
gets = lambda: list(map(int, input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]
h, N = gets()
AB = getss(N)
dp = [0] + [float("inf")] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print((dp[h]))

-import sys -import numpy as np - -h, n = list(map(int, input().split())) -ab = np.array(sys.stdin.read().split(), dtype=np.int64) -aaa = ab[0::2] -bbb = ab[1::2] -dp = np.zeros(10001, dtype=np.int64) -for i in range(1, h + 1): -    dp[i] = (dp[i - aaa] + bbb).min() +# coding=utf-8 +# Date: 2020-01-08 +# Author: lee215 +get = lambda: int(input().strip()) +getl = lambda: input().strip() +gets = lambda: list(map(int, input().strip().split())) +getss = lambda n: [gets() for _ in range(n)] +h, N = gets() +AB = getss(N) +dp = [0] + [float("inf")] * h +for a, b in AB: +    for i in range(h): +        j = min(i + a, h) +        dp[j] = min(dp[j], dp[i] + b) -# https://atcoder.jp/contests/abc153/submissions/9776226