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)
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)
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)

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)

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