def e_crested_ibis_vs_monster():

    H, N = [int(i) for i in input().split()]

    Damage, Cost = [], []

    for _ in range(N):

        a, b = [int(i) for i in input().split()]

        Damage.append(a)

        Cost.append(b)



    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値

    dp = [[float('inf')] * (H + 1) for _ in range(N + 1)]

    dp[0][0] = 0

    for i in range(N):

        for j in range(H + 1):

            # i 番目の魔法を使わない場合

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

            # i 番目の魔法を使う場合

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

                                                   dp[i + 1][j] + Cost[i])

    return dp[N][H]



print((e_crested_ibis_vs_monster()))
def e_crested_ibis_vs_monster():

    H, N = [int(i) for i in input().split()]

    Monsters = [[int(i) for i in input().split()] for j in range(N)]



    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値

    # としたとき、更新順序を工夫することで添字 i をなくせる

    dp = [0] + [float('inf')] * H

    for a, b in Monsters:

        for j in range(H + 1):

            nj = min(j + a, H)

            dp[nj] = min(dp[nj], dp[j] + b)

    return dp[H]



print((e_crested_ibis_vs_monster()))
def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Damage, Cost = [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        Damage.append(a)
        Cost.append(b)
    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    dp = [[float("inf")] * (H + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H + 1):
            # i 番目の魔法を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i 番目の魔法を使う場合
            dp[i + 1][min(j + Damage[i], H)] = min(
                dp[i + 1][min(j + Damage[i], H)], dp[i + 1][j] + Cost[i]
            )
    return dp[N][H]


print((e_crested_ibis_vs_monster()))

def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Monsters = [[int(i) for i in input().split()] for j in range(N)]
    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    # としたとき、更新順序を工夫することで添字 i をなくせる
    dp = [0] + [float("inf")] * H
    for a, b in Monsters:
        for j in range(H + 1):
            nj = min(j + a, H)
            dp[nj] = min(dp[nj], dp[j] + b)
    return dp[H]


print((e_crested_ibis_vs_monster()))

-    Damage, Cost = [], [] -    for _ in range(N): -        a, b = [int(i) for i in input().split()] -        Damage.append(a) -        Cost.append(b) +    Monsters = [[int(i) for i in input().split()] for j in range(N)] -    dp = [[float("inf")] * (H + 1) for _ in range(N + 1)] -    dp[0][0] = 0 -    for i in range(N): +    # としたとき、更新順序を工夫することで添字 i をなくせる +    dp = [0] + [float("inf")] * H +    for a, b in Monsters: -            # i 番目の魔法を使わない場合 -            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]) -            # i 番目の魔法を使う場合 -            dp[i + 1][min(j + Damage[i], H)] = min( -                dp[i + 1][min(j + Damage[i], H)], dp[i + 1][j] + Cost[i] -            ) -    return dp[N][H] +            nj = min(j + a, H) +            dp[nj] = min(dp[nj], dp[j] + b) +    return dp[H]