from sys import stdin

import numpy as np

from numba import njit



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

M = [list(map(int, stdin.readline().split())) for i in [0]*N]

M = np.array(M)



@njit

def main(h,n,m):

    dp = [10**8+1]*(10**4+1)

    dp = np.array(dp)

    dp[0] = 0



    for i in range(1,10**4+1):

        for j in range(n):

            a = m[j][0]

            b = m[j][1]

            if a>i:

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

            else:

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



    print((dp[h]))



if __name__=="__main__":

    main(H,N,M)
def getval():

    h,n = list(map(int,input().split()))

    m = [list(map(int,input().split())) for i in range(n)]

    return h,n,m



def main(h,n,m):

    #DP for minimal mp needed to do h damage

    dp = [0]

    for i in range(h):

        update = 2**60

        for j in m:

            if j[0]>=(i+1):

                update = min(update,j[1])

            else:

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

        dp.append(update)

    print((dp[h]))    

                

if __name__=="__main__":

    h,n,m = getval()

    main(h,n,m)
from sys import stdin
import numpy as np
from numba import njit

H, N = list(map(int, input().split()))
M = [list(map(int, stdin.readline().split())) for i in [0] * N]
M = np.array(M)


@njit
def main(h, n, m):
    dp = [10**8 + 1] * (10**4 + 1)
    dp = np.array(dp)
    dp[0] = 0
    for i in range(1, 10**4 + 1):
        for j in range(n):
            a = m[j][0]
            b = m[j][1]
            if a > i:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print((dp[h]))


if __name__ == "__main__":
    main(H, N, M)

def getval():
    h, n = list(map(int, input().split()))
    m = [list(map(int, input().split())) for i in range(n)]
    return h, n, m


def main(h, n, m):
    # DP for minimal mp needed to do h damage
    dp = [0]
    for i in range(h):
        update = 2**60
        for j in m:
            if j[0] >= (i + 1):
                update = min(update, j[1])
            else:
                update = min(update, j[1] + dp[i + 1 - j[0]])
        dp.append(update)
    print((dp[h]))


if __name__ == "__main__":
    h, n, m = getval()
    main(h, n, m)

-from sys import stdin -import numpy as np -from numba import njit - -H, N = list(map(int, input().split())) -M = [list(map(int, stdin.readline().split())) for i in [0] * N] -M = np.array(M) +def getval(): +    h, n = list(map(int, input().split())) +    m = [list(map(int, input().split())) for i in range(n)] +    return h, n, m -@njit -    dp = [10**8 + 1] * (10**4 + 1) -    dp = np.array(dp) -    dp[0] = 0 -    for i in range(1, 10**4 + 1): -        for j in range(n): -            a = m[j][0] -            b = m[j][1] -            if a > i: -                dp[i] = min(dp[i], b) +    # DP for minimal mp needed to do h damage +    dp = [0] +    for i in range(h): +        update = 2**60 +        for j in m: +            if j[0] >= (i + 1): +                update = min(update, j[1]) -                dp[i] = min(dp[i], dp[i - a] + b) +                update = min(update, j[1] + dp[i + 1 - j[0]]) +        dp.append(update) -    main(H, N, M) +    h, n, m = getval() +    main(h, n, m)