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

dp = [10 ** 18] * (H + 1)



dp[0] = 0



for i in range(N):

    a, b = list(map(int, input().split()))

    for j in range(H):

        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる

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



print((dp[H]))



def main():

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

    dp = [10 ** 18] * (H + 1)



    dp[0] = 0



    for i in range(N):

        a, b = list(map(int, input().split()))

        for j in range(H):

            nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる

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



    print((dp[H]))





main()

H, N = list(map(int, input().split()))
dp = [10**18] * (H + 1)
dp[0] = 0
for i in range(N):
    a, b = list(map(int, input().split()))
    for j in range(H):
        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
        dp[nj] = min(dp[nj], dp[j] + b)
print((dp[H]))

def main():
    H, N = list(map(int, input().split()))
    dp = [10**18] * (H + 1)
    dp[0] = 0
    for i in range(N):
        a, b = list(map(int, input().split()))
        for j in range(H):
            nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
            dp[nj] = min(dp[nj], dp[j] + b)
    print((dp[H]))


main()

-H, N = list(map(int, input().split())) -dp = [10**18] * (H + 1) -dp[0] = 0 -for i in range(N): -    a, b = list(map(int, input().split())) -    for j in range(H): -        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる -        dp[nj] = min(dp[nj], dp[j] + b) -print((dp[H])) +def main(): +    H, N = list(map(int, input().split())) +    dp = [10**18] * (H + 1) +    dp[0] = 0 +    for i in range(N): +        a, b = list(map(int, input().split())) +        for j in range(H): +            nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる +            dp[nj] = min(dp[nj], dp[j] + b) +    print((dp[H])) + + +main()