def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10**7)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations, accumulate, groupby, product

    from bisect import bisect_left,bisect_right

    from heapq import heapify, heappop, heappush

    from math import floor, ceil

    #from operator import itemgetter



    inf = 10**17

    #mod = 10**9 + 7



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

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

    dp = [inf] * (3*(10**4))

    dp[0] = 0

    for i in range(3*(10**4)):

        for a,b in ab:

            if i-a >= 0:

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

    res = inf

    for i in range(h, 3*(10**4)):

        res = min(res, dp[i])

    print(res)



if __name__ == '__main__':

    main()
def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10**7)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations, accumulate, groupby, product

    from bisect import bisect_left,bisect_right

    from heapq import heapify, heappop, heappush

    from math import floor, ceil

    #from operator import itemgetter



    inf = 10**17

    #mod = 10**9 + 7



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

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

    dp = [inf] * (h+1)

    dp[0] = 0

    for i in range(h+1):

        for a,b in ab:

            if i+a > h:

                c = h

            else:

                c = i + a

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



    print((dp[-1]))



if __name__ == '__main__':

    main()

def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left, bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil

    # from operator import itemgetter
    inf = 10**17
    # mod = 10**9 + 7
    h, n = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp = [inf] * (3 * (10**4))
    dp[0] = 0
    for i in range(3 * (10**4)):
        for a, b in ab:
            if i - a >= 0:
                dp[i] = min(dp[i], dp[i - a] + b)
    res = inf
    for i in range(h, 3 * (10**4)):
        res = min(res, dp[i])
    print(res)


if __name__ == "__main__":
    main()

def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left, bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil

    # from operator import itemgetter
    inf = 10**17
    # mod = 10**9 + 7
    h, n = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp = [inf] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        for a, b in ab:
            if i + a > h:
                c = h
            else:
                c = i + a
            dp[c] = min(dp[c], dp[i] + b)
    print((dp[-1]))


if __name__ == "__main__":
    main()

-    dp = [inf] * (3 * (10**4)) +    dp = [inf] * (h + 1) -    for i in range(3 * (10**4)): +    for i in range(h + 1): -            if i - a >= 0: -                dp[i] = min(dp[i], dp[i - a] + b) -    res = inf -    for i in range(h, 3 * (10**4)): -        res = min(res, dp[i]) -    print(res) +            if i + a > h: +                c = h +            else: +                c = i + a +            dp[c] = min(dp[c], dp[i] + b) +    print((dp[-1]))