#n=int(input())

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

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

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

#l=[list(input().split()) for i in range(n)]



amax=0

for i in range(n):

    if amax<l[i][0]:

        amax=l[i][0]

        

ldp=[[0 for j in range(h+amax)]for i in range(n)]

for i in range(n):

    for j in range(h+amax):

        if i==0:

            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]

        else:

            if j>=l[i][0]:

                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])

            else:

                ldp[i][j]=min(ldp[i-1][j],l[i][1])

print((min(ldp[-1][h-1:])))
#n=int(input())

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

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

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

#l=[list(input().split()) for i in range(n)]





        

ldp=[[0 for j in range(h)]for i in range(n)]

for i in range(n):

    for j in range(h):

        if i==0:

            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]

        else:

            if j>=l[i][0]:

                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])

            else:

                ldp[i][j]=min(ldp[i-1][j],l[i][1])

print((ldp[-1][-1]))

# n=int(input())
h, n = list(map(int, input().split()))
# a=list(map(int,input().split()))
l = [list(map(int, input().split())) for i in range(n)]
# l=[list(input().split()) for i in range(n)]
amax = 0
for i in range(n):
    if amax < l[i][0]:
        amax = l[i][0]
ldp = [[0 for j in range(h + amax)] for i in range(n)]
for i in range(n):
    for j in range(h + amax):
        if i == 0:
            ldp[i][j] = -(-(j + 1) // l[i][0]) * l[i][1]
        else:
            if j >= l[i][0]:
                ldp[i][j] = min(ldp[i - 1][j], ldp[i][j - l[i][0]] + l[i][1])
            else:
                ldp[i][j] = min(ldp[i - 1][j], l[i][1])
print((min(ldp[-1][h - 1 :])))

# n=int(input())
h, n = list(map(int, input().split()))
# a=list(map(int,input().split()))
l = [list(map(int, input().split())) for i in range(n)]
# l=[list(input().split()) for i in range(n)]
ldp = [[0 for j in range(h)] for i in range(n)]
for i in range(n):
    for j in range(h):
        if i == 0:
            ldp[i][j] = -(-(j + 1) // l[i][0]) * l[i][1]
        else:
            if j >= l[i][0]:
                ldp[i][j] = min(ldp[i - 1][j], ldp[i][j - l[i][0]] + l[i][1])
            else:
                ldp[i][j] = min(ldp[i - 1][j], l[i][1])
print((ldp[-1][-1]))

-amax = 0 +ldp = [[0 for j in range(h)] for i in range(n)] -    if amax < l[i][0]: -        amax = l[i][0] -ldp = [[0 for j in range(h + amax)] for i in range(n)] -for i in range(n): -    for j in range(h + amax): +    for j in range(h): -print((min(ldp[-1][h - 1 :]))) +print((ldp[-1][-1]))