#coding:utf-8



def main():

    h, n = list(map(int, input().split()))

    ab = []

    for _ in range(n):

        ab.append(list(map(int, input().split())))

    

    inf = 100000000000

    # indexがモンスターに与えたダメージで、中身がトキのダメージ

    damages = [0] + [inf] * h

    for i in range(1, h + 1):

        for j in range(n):

            damage_monster = ab[j][0]

            damage_toki = ab[j][1]

            

            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])





    print((min(damages[h:])))

main()
#coding:utf-8

 

def main():

    h, n = list(map(int, input().split()))

    ab = []

    for _ in range(n):

        ab.append(list(map(int, input().split())))

    

    inf = 100000000000

    # indexがモンスターに与えたダメージで、中身がトキのダメージ

    damages = [inf for _ in range(100000)]

    damages[0] = 0

    pre_damage = -1

    for i in range(h):

        if damages[i] == inf:

            continue

        for j in range(n):

            new_damage = ab[j][0]

            if damages[i + new_damage] > damages[i] + ab[j][1]:

                damages[i + new_damage] = damages[i] + ab[j][1]

        

 

    print((min(damages[h:])))

main()
# coding:utf-8
def main():
    h, n = list(map(int, input().split()))
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            damages[i] = min(
                damages[max(0, i - damage_monster)] + damage_toki, damages[i]
            )
    print((min(damages[h:])))


main()

# coding:utf-8
def main():
    h, n = list(map(int, input().split()))
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    pre_damage = -1
    for i in range(h):
        if damages[i] == inf:
            continue
        for j in range(n):
            new_damage = ab[j][0]
            if damages[i + new_damage] > damages[i] + ab[j][1]:
                damages[i + new_damage] = damages[i] + ab[j][1]
    print((min(damages[h:])))


main()

-    damages = [0] + [inf] * h -    for i in range(1, h + 1): +    damages = [inf for _ in range(100000)] +    damages[0] = 0 +    pre_damage = -1 +    for i in range(h): +        if damages[i] == inf: +            continue -            damage_monster = ab[j][0] -            damage_toki = ab[j][1] -            damages[i] = min( -                damages[max(0, i - damage_monster)] + damage_toki, damages[i] -            ) +            new_damage = ab[j][0] +            if damages[i + new_damage] > damages[i] + ab[j][1]: +                damages[i + new_damage] = damages[i] + ab[j][1]