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



dg = 10**5



ba = []

for _ in [0]*n:

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

    if a >= h:

        a = h

    ba.append(b*dg+a)

ba.sort()



d = [10**9]*(h+1)



d[0] = 0



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

    for e in ba:

        a,b = e%dg,e//dg

        if i<=a:

            if d[i] > b:

                d[i] = b

        else:

            if d[i] > d[i-a]+b:

                d[i] = d[i-a]+b



print((d[-1]))
import sys

input = sys.stdin.readline



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



dg = 10**5



ba = []

for _ in [0]*n:

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

    if a >= h:

        a = h

    ba.append(b*dg+a)

ba.sort()



d = [10**9]*(h+1)



d[0] = 0



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

    for e in ba:

        a,b = e%dg,e//dg

        if i<=a:

            if d[i] > b:

                d[i] = b

        else:

            if d[i] > d[i-a]+b:

                d[i] = d[i-a]+b



print((d[-1]))

h, n = list(map(int, input().split()))
dg = 10**5
ba = []
for _ in [0] * n:
    a, b = list(map(int, input().split()))
    if a >= h:
        a = h
    ba.append(b * dg + a)
ba.sort()
d = [10**9] * (h + 1)
d[0] = 0
for i in range(1, h + 1):
    for e in ba:
        a, b = e % dg, e // dg
        if i <= a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i - a] + b:
                d[i] = d[i - a] + b
print((d[-1]))

import sys

input = sys.stdin.readline
h, n = list(map(int, input().split()))
dg = 10**5
ba = []
for _ in [0] * n:
    a, b = list(map(int, input().split()))
    if a >= h:
        a = h
    ba.append(b * dg + a)
ba.sort()
d = [10**9] * (h + 1)
d[0] = 0
for i in range(1, h + 1):
    for e in ba:
        a, b = e % dg, e // dg
        if i <= a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i - a] + b:
                d[i] = d[i - a] + b
print((d[-1]))

+import sys + +input = sys.stdin.readline