def main():

    h,n,*t=list(map(int,open(0).read().split()))

    d=[0]+[10**18]*h

    for a,b in zip(*[iter(t)]*2):

        for j in range(h+1):

            k=j-a

            if k<0:k=0

            c=d[k]+b

            if c<d[j]:d[j]=c

    print((d[h]))

main()
intLine=lambda:list(map(int,input().split()))

h,n=intLine()

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

dp[0]=0

for _ in range(n):

  a,b=intLine()

  for j in range(h+1):

    dp[j]=min(dp[j],dp[max(0,j-a)]+b)

print((dp[h]))
def main():
    h, n, *t = list(map(int, open(0).read().split()))
    d = [0] + [10**18] * h
    for a, b in zip(*[iter(t)] * 2):
        for j in range(h + 1):
            k = j - a
            if k < 0:
                k = 0
            c = d[k] + b
            if c < d[j]:
                d[j] = c
    print((d[h]))


main()

intLine = lambda: list(map(int, input().split()))
h, n = intLine()
dp = [10**9] * (h + 1)
dp[0] = 0
for _ in range(n):
    a, b = intLine()
    for j in range(h + 1):
        dp[j] = min(dp[j], dp[max(0, j - a)] + b)
print((dp[h]))

-def main(): -    h, n, *t = list(map(int, open(0).read().split())) -    d = [0] + [10**18] * h -    for a, b in zip(*[iter(t)] * 2): -        for j in range(h + 1): -            k = j - a -            if k < 0: -                k = 0 -            c = d[k] + b -            if c < d[j]: -                d[j] = c -    print((d[h])) - - -main() +intLine = lambda: list(map(int, input().split())) +h, n = intLine() +dp = [10**9] * (h + 1) +dp[0] = 0 +for _ in range(n): +    a, b = intLine() +    for j in range(h + 1): +        dp[j] = min(dp[j], dp[max(0, j - a)] + b) +print((dp[h]))