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]))

import sys





def solve(h, n, ab):

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

    INF = 10 ** 18

    cache = {}

    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく

    best = ((h - 1) // ab[0][0] + 1) * ab[0][1]



    def dp(k, i=0, cost=0):

        nonlocal best

        if k <= 0:

            return cost

        if (k, i) in cache:

            return cache[k, i] + cost

        a, b = ab[i]

        if k / a * b + cost >= best:

            # どう足掻いても残りでbestより良い結果は得られない

            return INF

        c = (k - 1) // a + 1

        if i == n - 1:

            ret = cost + b * c

        else:

            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1))

        cache[k, i] = ret - cost

        best = min(best, ret)

        return ret



    dp(h)

    return best





sys.setrecursionlimit(10001)



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

ab = [tuple(map(int, line.split())) for line in sys.stdin]

print((solve(h, n, ab)))

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]))

import sys


def solve(h, n, ab):
    ab.sort(key=lambda x: x[1] / x[0])
    INF = 10**18
    cache = {}
    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく
    best = ((h - 1) // ab[0][0] + 1) * ab[0][1]

    def dp(k, i=0, cost=0):
        nonlocal best
        if k <= 0:
            return cost
        if (k, i) in cache:
            return cache[k, i] + cost
        a, b = ab[i]
        if k / a * b + cost >= best:
            # どう足掻いても残りでbestより良い結果は得られない
            return INF
        c = (k - 1) // a + 1
        if i == n - 1:
            ret = cost + b * c
        else:
            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1))
        cache[k, i] = ret - cost
        best = min(best, ret)
        return ret

    dp(h)
    return best


sys.setrecursionlimit(10001)
h, n = list(map(int, input().split()))
ab = [tuple(map(int, line.split())) for line in sys.stdin]
print((solve(h, n, ab)))

-import numpy as np + +def solve(h, n, ab): +    ab.sort(key=lambda x: x[1] / x[0]) +    INF = 10**18 +    cache = {} +    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく +    best = ((h - 1) // ab[0][0] + 1) * ab[0][1] + +    def dp(k, i=0, cost=0): +        nonlocal best +        if k <= 0: +            return cost +        if (k, i) in cache: +            return cache[k, i] + cost +        a, b = ab[i] +        if k / a * b + cost >= best: +            # どう足掻いても残りでbestより良い結果は得られない +            return INF +        c = (k - 1) // a + 1 +        if i == n - 1: +            ret = cost + b * c +        else: +            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1)) +        cache[k, i] = ret - cost +        best = min(best, ret) +        return ret + +    dp(h) +    return best + + +sys.setrecursionlimit(10001) -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])) +ab = [tuple(map(int, line.split())) for line in sys.stdin] +print((solve(h, n, ab)))