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

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



INF=10**9



dp=[INF for _ in range(H+1)]

dp[H]=0

for h in range(H,0,-1):

    for n in range(N):

        A,B=AB[n]

        newH=max(0,h-A)

        dp[newH]=min(dp[newH], dp[h]+B)



print((dp[0]))
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)

import sys

def main(H, N, AB):

    INF = 10**9

    dp = [INF] * (H + 1)

    dp[H] = 0

    for h in reversed(list(range(H + 1))):

        for i, (a, b) in enumerate(AB):

            nh = max(0, h - a)

            dp[nh] = min(dp[nh], dp[h] + b)

    print((dp[0]))



if __name__ == '__main__':

    input = sys.stdin.readline

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

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

    main(H, N, AB)

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
INF = 10**9
dp = [INF for _ in range(H + 1)]
dp[H] = 0
for h in range(H, 0, -1):
    for n in range(N):
        A, B = AB[n]
        newH = max(0, h - A)
        dp[newH] = min(dp[newH], dp[h] + B)
print((dp[0]))

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys


def main(H, N, AB):
    INF = 10**9
    dp = [INF] * (H + 1)
    dp[H] = 0
    for h in reversed(list(range(H + 1))):
        for i, (a, b) in enumerate(AB):
            nh = max(0, h - a)
            dp[nh] = min(dp[nh], dp[h] + b)
    print((dp[0]))


if __name__ == "__main__":
    input = sys.stdin.readline
    H, N = list(map(int, input().split()))
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    main(H, N, AB)

-H, N = list(map(int, input().split())) -AB = [list(map(int, input().split())) for _ in range(N)] -INF = 10**9 -dp = [INF for _ in range(H + 1)] -dp[H] = 0 -for h in range(H, 0, -1): -    for n in range(N): -        A, B = AB[n] -        newH = max(0, h - A) -        dp[newH] = min(dp[newH], dp[h] + B) -print((dp[0])) +# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..) +import sys + + +def main(H, N, AB): +    INF = 10**9 +    dp = [INF] * (H + 1) +    dp[H] = 0 +    for h in reversed(list(range(H + 1))): +        for i, (a, b) in enumerate(AB): +            nh = max(0, h - a) +            dp[nh] = min(dp[nh], dp[h] + b) +    print((dp[0])) + + +if __name__ == "__main__": +    input = sys.stdin.readline +    H, N = list(map(int, input().split())) +    AB = [tuple(map(int, input().split())) for _ in range(N)] +    main(H, N, AB)