def main():

    from sys import stdin

    readline = stdin.readline

    H, N = list(map(int, readline().split()))

    AB = [list(map(int, readline().split())) for _ in range(N)]



    dp = [100000000] * (H + 10 ** 4 + 1)

    dp[0] = 0

    for i in range(H):

        if dp[i] == 100000000:

            continue

        for a, b in AB:

            t = dp[i] + b

            if t < dp[i + a]:

                dp[i + a] = t

    print((min(dp[H:])))





main()

H, N = list(map(int, input().split()))

AB = [list(map(int, input().split())) for _ in range(N)]



A_max = 10 ** 4

INF = float('inf')



dp = [INF] * (H + A_max + 1)

dp[0] = 0

for i in range(H):

    if dp[i] == INF:

        continue

    for a, b in AB:

        if dp[i] + b < dp[i + a]:

            dp[i + a] = dp[i] + b

print((min(dp[H:])))

def main():
    from sys import stdin

    readline = stdin.readline
    H, N = list(map(int, readline().split()))
    AB = [list(map(int, readline().split())) for _ in range(N)]
    dp = [100000000] * (H + 10**4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print((min(dp[H:])))


main()

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
A_max = 10**4
INF = float("inf")
dp = [INF] * (H + A_max + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == INF:
        continue
    for a, b in AB:
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print((min(dp[H:])))

-def main(): -    from sys import stdin - -    readline = stdin.readline -    H, N = list(map(int, readline().split())) -    AB = [list(map(int, readline().split())) for _ in range(N)] -    dp = [100000000] * (H + 10**4 + 1) -    dp[0] = 0 -    for i in range(H): -        if dp[i] == 100000000: -            continue -        for a, b in AB: -            t = dp[i] + b -            if t < dp[i + a]: -                dp[i + a] = t -    print((min(dp[H:]))) - - -main() +H, N = list(map(int, input().split())) +AB = [list(map(int, input().split())) for _ in range(N)] +A_max = 10**4 +INF = float("inf") +dp = [INF] * (H + A_max + 1) +dp[0] = 0 +for i in range(H): +    if dp[i] == INF: +        continue +    for a, b in AB: +        if dp[i] + b < dp[i + a]: +            dp[i + a] = dp[i] + b +print((min(dp[H:])))