INF = 10 ** 9



def main():

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

    dp = [INF] * (H+1)

    dp[0] = 0

    for _ in range(N):

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

        for j in range(H):

            nj = min(j+a, H)

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



    print((dp[H]))



    

if __name__ == "__main__":

    main()
import sys

readline = sys.stdin.readline

INF = 10 ** 8





def main():

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

    dp = [INF] * (H + 1)  # HPを減らすのに必要な最小のMP

    dp[0] = 0



    for _ in range(N):

        hp, mp = list(map(int, readline().rstrip().split()))



        for i in range(H):

            j = min(i+hp, H)

            dp[j] = min(dp[j], dp[i] + mp)



    print((dp[-1]))





if __name__ == '__main__':

    main()
INF = 10**9


def main():
    H, N = list(map(int, input().split()))
    dp = [INF] * (H + 1)
    dp[0] = 0
    for _ in range(N):
        a, b = list(map(int, input().split()))
        for j in range(H):
            nj = min(j + a, H)
            dp[nj] = min(dp[nj], dp[j] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()

import sys

readline = sys.stdin.readline
INF = 10**8


def main():
    H, N = list(map(int, readline().rstrip().split()))
    dp = [INF] * (H + 1)  # HPを減らすのに必要な最小のMP
    dp[0] = 0
    for _ in range(N):
        hp, mp = list(map(int, readline().rstrip().split()))
        for i in range(H):
            j = min(i + hp, H)
            dp[j] = min(dp[j], dp[i] + mp)
    print((dp[-1]))


if __name__ == "__main__":
    main()

-INF = 10**9 +import sys + +readline = sys.stdin.readline +INF = 10**8 -    H, N = list(map(int, input().split())) -    dp = [INF] * (H + 1) +    H, N = list(map(int, readline().rstrip().split())) +    dp = [INF] * (H + 1)  # HPを減らすのに必要な最小のMP -        a, b = list(map(int, input().split())) -        for j in range(H): -            nj = min(j + a, H) -            dp[nj] = min(dp[nj], dp[j] + b) -    print((dp[H])) +        hp, mp = list(map(int, readline().rstrip().split())) +        for i in range(H): +            j = min(i + hp, H) +            dp[j] = min(dp[j], dp[i] + mp) +    print((dp[-1]))