#import sys

MOD = 10 ** 9 + 7

INFI = 10**10

#input = sys.stdin.readline

import math

 

import itertools

 

#import bisect

 

import copy

 

 

def sosuhante(n):

    for k in range(2, int(math.sqrt(n))+1):

        if n% k ==0:

            return False

    return True

def cmb(n, r):

    if n - r < r: r = n - r

    if r == 0: return 1

    if r == 1: return n

 

    numerator = [n - r + k + 1 for k in range(r)]

    denominator = [k + 1 for k in range(r)]

 

    for p in range(2,r+1):

        pivot = denominator[p - 1]

        if pivot > 1:

            offset = (n - r) % p

            for k in range(p-1,r,p):

                numerator[k - offset] /= pivot

                denominator[k] /= pivot

 

    result = 1

    for k in range(r):

        if numerator[k] > 1:

            result *= int(numerator[k])

 

    return result

 

def kingaku(a,b,n):

    keta=len(str(n))

    return a*n+b*keta

 

def my_index(l, x, default=False):

    if x in l:

        return l.index(x)

    else:

        return default

 

#    h,w,a,b = map(int, input().split())

#    c = [[0 for j in range(n)] for i in range(n)]

 

 

 

def main():

    h,n=list(map(int,input().split())) #n yen, m types

    a=[]

    b=[]

    for i in range(n):

        x,y=list(map(int,input().split()))

        a.append(x)

        b.append(y)

 

    dp=[INFI for i in range(h+1)]

    dp[0]=0

    for i in range(n):

        for j in range(len(dp)):

            if j-a[i]<0:

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

            else:

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

 

    print((dp[h]))

 

 

if __name__ == "__main__":

    main()
#import sys

MOD = 10 ** 9 + 7

INFI = 10**10

#input = sys.stdin.readline

import math

 

import itertools

 

#import bisect

 

import copy

from functools import lru_cache

 

def sosuhante(n):

    for k in range(2, int(math.sqrt(n))+1):

        if n% k ==0:

            return False

    return True

def cmb(n, r):

    if n - r < r: r = n - r

    if r == 0: return 1

    if r == 1: return n

 

    numerator = [n - r + k + 1 for k in range(r)]

    denominator = [k + 1 for k in range(r)]

 

    for p in range(2,r+1):

        pivot = denominator[p - 1]

        if pivot > 1:

            offset = (n - r) % p

            for k in range(p-1,r,p):

                numerator[k - offset] /= pivot

                denominator[k] /= pivot

 

    result = 1

    for k in range(r):

        if numerator[k] > 1:

            result *= int(numerator[k])

 

    return result

 

def kingaku(a,b,n):

    keta=len(str(n))

    return a*n+b*keta

 

def my_index(l, x, default=False):

    if x in l:

        return l.index(x)

    else:

        return default

 

#    h,w,a,b = map(int, input().split())

#    c = [[0 for j in range(n)] for i in range(n)]

 

 

 

def main():

    h,n=list(map(int,input().split())) #n yen, m types

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

    maxa = max(a for a, b in ab)

    dp=[INFI for i in range(h+maxa)]

    dp[0]=0

 

 

    def f(h):

 

        for a,b in ab:

            for j in range(h+maxa):

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

        return min(dp[h:])

 

    print((f(h)))

 

 

if __name__ == "__main__":

    main()
# import sys
MOD = 10**9 + 7
INFI = 10**10
# input = sys.stdin.readline
import math
import itertools

# import bisect
import copy


def sosuhante(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result


def kingaku(a, b, n):
    keta = len(str(n))
    return a * n + b * keta


def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    h, n = list(map(int, input().split()))  # n yen, m types
    a = []
    b = []
    for i in range(n):
        x, y = list(map(int, input().split()))
        a.append(x)
        b.append(y)
    dp = [INFI for i in range(h + 1)]
    dp[0] = 0
    for i in range(n):
        for j in range(len(dp)):
            if j - a[i] < 0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j] = min(dp[j], dp[j - a[i]] + b[i])
    print((dp[h]))


if __name__ == "__main__":
    main()

# import sys
MOD = 10**9 + 7
INFI = 10**10
# input = sys.stdin.readline
import math
import itertools

# import bisect
import copy
from functools import lru_cache


def sosuhante(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result


def kingaku(a, b, n):
    keta = len(str(n))
    return a * n + b * keta


def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    h, n = list(map(int, input().split()))  # n yen, m types
    ab = [list(map(int, input().split())) for i in range(n)]
    maxa = max(a for a, b in ab)
    dp = [INFI for i in range(h + maxa)]
    dp[0] = 0

    def f(h):
        for a, b in ab:
            for j in range(h + maxa):
                dp[j] = min(dp[j], dp[j - a] + b)
        return min(dp[h:])

    print((f(h)))


if __name__ == "__main__":
    main()

+from functools import lru_cache -    a = [] -    b = [] -    for i in range(n): -        x, y = list(map(int, input().split())) -        a.append(x) -        b.append(y) -    dp = [INFI for i in range(h + 1)] +    ab = [list(map(int, input().split())) for i in range(n)] +    maxa = max(a for a, b in ab) +    dp = [INFI for i in range(h + maxa)] -    for i in range(n): -        for j in range(len(dp)): -            if j - a[i] < 0: -                dp[j] = min(dp[j], dp[0] + b[i]) -            else: -                dp[j] = min(dp[j], dp[j - a[i]] + b[i]) -    print((dp[h])) + +    def f(h): +        for a, b in ab: +            for j in range(h + maxa): +                dp[j] = min(dp[j], dp[j - a] + b) +        return min(dp[h:]) + +    print((f(h)))