# E - Crested Ibis vs Monster

from collections import defaultdict





def main():

    H, N, *AB = list(map(int, open(0).read().split()))

    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i

    dp[0] = 0

    for i in range(H):

        if i not in dp:

            continue

        for a, b in zip(*[iter(AB)] * 2):

            if i + a < H:

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

            else:

                dp[H] = min(dp[H], dp[i] + b)

    print((dp[H]))





if __name__ == "__main__":

    main()

# E - Crested Ibis vs Monster

def main():

    INF = 1 << 30

    

    H, N, *AB = list(map(int, open(0).read().split()))

    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i

    dp[0] = 0

    for i in range(H):

        if dp[i] == INF:

            continue

        for a, b in zip(*[iter(AB)] * 2):

            if i + a < H:

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

            else:

                dp[H] = min(dp[H], dp[i] + b)

    print((dp[H]))





if __name__ == "__main__":

    main()

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = defaultdict(
        lambda: 1 << 30
    )  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if i not in dp:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()

-from collections import defaultdict - - +    INF = 1 << 30 -    dp = defaultdict( -        lambda: 1 << 30 -    )  # dp[i] := min magic points to decrease monster's health by i +    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i -        if i not in dp: +        if dp[i] == INF: