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,defaultdict,Counter

from heapq import heapify,heappop,heappush,heappushpop

from copy import copy,deepcopy

from itertools import product,permutations,combinations,combinations_with_replacement

from bisect import bisect_left,bisect_right

from math import sqrt,gcd,ceil,floor,factorial

# from fractions import gcd

from functools import reduce

from pprint import pprint

from statistics import mean,median,mode

import sys

sys.setrecursionlimit(10 ** 6)



INF = float("inf")



def mycol(data,col):

    return [ row[col] for row in data ]



def mysort(data,col,reverse=False):

    data.sort(key=lambda x:x[col],reverse=revese)

    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 mycount(ls,x):

    # lsはソート済みであること

    l = bisect_left(ls,x)

    r = bisect_right(ls,x)

    return (r-l)



def mydictvaluesort(dictionary):

    return sorted( list(dictionary.items()), key=lambda x:x[1] )



def mydictkeysort(dictionary):

    return sorted( list(dictionary.items()), key=lambda x:x[0] )



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



def I():

    return int(eval(input()))



def MI():

    return list(map(int,input().split()))



def RI():

    return list(map(int,input().split()))



def CI(n):

    return [ int(eval(input())) for _ in range(n) ]



def LI(n):

    return [ list(map(int,input().split())) for _ in range(n) ]



def S():

    return eval(input())



def MS():

    return input().split()



def RS():

    return list(eval(input()))



def CS(n):

    return [ eval(input()) for _ in range(n) ]



def LS(n):

    return [ list(eval(input())) for _ in range(n) ]



# ddict = defaultdict(lambda: 0)

# ddict = defaultdict(lambda: 1)

# ddict = defaultdict(lambda: int())

# ddict = defaultdict(lambda: list())

# ddict = defaultdict(lambda: float())



h,n = MI()

ab = LI(n)



# dp[i][j]:i番目までの魔法の中から削る体力がj以上になるように選んだ時の消耗魔力の最小値

dp = [ [INF]*(h+1) for _ in range(n+1) ]

dp[0][0] = 0



for i in range(n):

    a = ab[i][0]

    b = ab[i][1]

    for j in range(h+1):

        if j<a:

            dp[i+1][j] = min( dp[i][j], b )

        else:

            dp[i+1][j] = min( dp[i][j], dp[i+1][j-a]+b )

# print(dp)

print((dp[n][h]))
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, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop
from copy import copy, deepcopy
from itertools import product, permutations, combinations, combinations_with_replacement
from bisect import bisect_left, bisect_right
from math import sqrt, gcd, ceil, floor, factorial

# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean, median, mode
import sys

sys.setrecursionlimit(10**6)
INF = float("inf")


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


def mysort(data, col, reverse=False):
    data.sort(key=lambda x: x[col], reverse=revese)
    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 mycount(ls, x):
    # lsはソート済みであること
    l = bisect_left(ls, x)
    r = bisect_right(ls, x)
    return r - l


def mydictvaluesort(dictionary):
    return sorted(list(dictionary.items()), key=lambda x: x[1])


def mydictkeysort(dictionary):
    return sorted(list(dictionary.items()), key=lambda x: x[0])


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


def I():
    return int(eval(input()))


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


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


def CI(n):
    return [int(eval(input())) for _ in range(n)]


def LI(n):
    return [list(map(int, input().split())) for _ in range(n)]


def S():
    return eval(input())


def MS():
    return input().split()


def RS():
    return list(eval(input()))


def CS(n):
    return [eval(input()) for _ in range(n)]


def LS(n):
    return [list(eval(input())) for _ in range(n)]


# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())
h, n = MI()
ab = LI(n)
# dp[i][j]:i番目までの魔法の中から削る体力がj以上になるように選んだ時の消耗魔力の最小値
dp = [[INF] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    for j in range(h + 1):
        if j < a:
            dp[i + 1][j] = min(dp[i][j], b)
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b)
# print(dp)
print((dp[n][h]))

-from collections import deque +from collections import deque, defaultdict, Counter -from itertools import permutations, combinations -from collections import defaultdict, Counter +from itertools import product, permutations, combinations, combinations_with_replacement +from math import sqrt, gcd, ceil, floor, factorial -# from math import gcd,ceil,floor,factorial +from statistics import mean, median, mode +import sys - -def myinput(): -    return list(map(int, input().split())) - - -def mylistinput(n): -    return [list(myinput()) for _ in range(n)] +sys.setrecursionlimit(10**6) +INF = float("inf") -def mysort(data, col, reverse_flag): -    data.sort(key=lambda x: x[col], reverse=reverse_flag) +def mysort(data, col, reverse=False): +    data.sort(key=lambda x: x[col], reverse=revese) + + +def mycount(ls, x): +    # lsはソート済みであること +    l = bisect_left(ls, x) +    r = bisect_right(ls, x) +    return r - l + + +def mydictvaluesort(dictionary): +    return sorted(list(dictionary.items()), key=lambda x: x[1]) + + +def mydictkeysort(dictionary): +    return sorted(list(dictionary.items()), key=lambda x: x[0]) -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) +def I(): +    return int(eval(input())) + + +def MI(): +    return list(map(int, input().split())) + + +def RI(): +    return list(map(int, input().split())) + + +def CI(n): +    return [int(eval(input())) for _ in range(n)] + + +def LI(n): +    return [list(map(int, input().split())) for _ in range(n)] + + +def S(): +    return eval(input()) + + +def MS(): +    return input().split() + + +def RS(): +    return list(eval(input())) + + +def CS(n): +    return [eval(input()) for _ in range(n)] + + +def LS(n): +    return [list(eval(input())) for _ in range(n)] + + +# ddict = defaultdict(lambda: 0) +# ddict = defaultdict(lambda: 1) +# ddict = defaultdict(lambda: int()) +# ddict = defaultdict(lambda: list()) +# ddict = defaultdict(lambda: float()) +h, n = MI() +ab = LI(n) +# dp[i][j]:i番目までの魔法の中から削る体力がj以上になるように選んだ時の消耗魔力の最小値 +dp = [[INF] * (h + 1) for _ in range(n + 1)] +dp[0][0] = 0 +for i in range(n): +    a = ab[i][0] +    b = ab[i][1] +    for j in range(h + 1): +        if j < a: +            dp[i + 1][j] = min(dp[i][j], b) -            dp[i] = min(dp[i], dp[i - a] + b) +            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b) -ans = dp[H] -print(ans) +print((dp[n][h]))