def main():

    import sys

    readline = sys.stdin.readline

    # readlines = sys.stdin.readlines

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

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

    INF = float('inf')

    dp = [INF] * (H + 1)

    dp[0] = 0

    

    for i in range(N):

        a, b = M[i]

        for j in range(H):

            nj = min(H, j + a)

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



    print((dp[H]))





if __name__ == "__main__":

    main()

def main():

    import sys

    readline = sys.stdin.readline

    # readlines = sys.stdin.readlines

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

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

    INF = 10 ** 9

    dp = [INF] * (H + 1)

    dp[0] = 0

    

    for i in range(N):

        a, b = M[i]

        for j in range(H):

            nj = min(H, j + a)

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



    print((dp[H]))





if __name__ == "__main__":

    main()

def main():
    import sys

    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    H, N = list(map(int, input().split()))
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = float("inf")
    dp = [INF] * (H + 1)
    dp[0] = 0
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()

def main():
    import sys

    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    H, N = list(map(int, input().split()))
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = 10**9
    dp = [INF] * (H + 1)
    dp[0] = 0
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()

-    INF = float("inf") +    INF = 10**9