# Original solution
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return list(map(int,input().split()))

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print((" ".join(ls)))
        elif type(ls[0])==int:
            print((" ".join(map(str,ls))))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print(("".join(ls)))
        elif type(ls[0])==int:
            print(("".join(map(str,ls))))
        else:
            print("Output Error")

H,N = myinput()
AB = mylistinput(N)

AB_sorted = mysort(AB,0,True)
# pprint(AB_sorted)
maxA = AB[0][0]
# print(maxA)
HA = H+maxA

# dp[i]: 敵の体力をiだけ減らすとしたときの，消耗魔力累計値の最小値
dp = [float("inf")]*(H+1)
dp[0] = 0

for i in range(1,H+1):
    for j in range(N):
        a = AB[j][0]
        b = AB[j][1]
        if i<a:
            dp[i] = min( dp[i], dp[0]+b )
        else:
            dp[i] = min( dp[i], dp[i-a]+b )
# print(dp)
ans = dp[H]
print(ans)

# Optimized solution
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return list(map(int,input().split()))

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print((" ".join(ls)))
        elif type(ls[0])==int:
            print((" ".join(map(str,ls))))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print(("".join(ls)))
        elif type(ls[0])==int:
            print(("".join(map(str,ls))))
        else:
            print("Output Error")

H,N = myinput()
AB = mylistinput(N)

# dp[i]: 敵の体力をiだけ減らすとしたときの，消耗魔力累計値の最小値
dp = [float("inf")]*(H+1)
dp[0] = 0

for i in range(1,H+1):
    for j in range(N):
        a = AB[j][0]
        b = AB[j][1]
        if i<a:
            dp[i] = min( dp[i], dp[0]+b )
        else:
            dp[i] = min( dp[i], dp[i-a]+b )
# print(dp)
ans = dp[H]
print(ans)