

def resolve():

    INF = 1<<60

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

    A, B = [], []

    for i in range(N):

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

        A.append(a)

        B.append(b)



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

    dp[0][0] = 0



    for i in range(N):

        for j in range(H+1):

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

            dp[i+1][min( j + A[ i ], H)] = min(dp[i+1][min( j + A[ i ], H)], dp[i+1][j] + B[i])

    print((dp[N][H]))





if __name__ == "__main__":

    resolve()



def resolve():

    INF = 1<<60

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

    A, B = [], []

    for i in range(N):

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

        A.append(a)

        B.append(b)



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

    for i in range(N):

        dp[i][0] = 0

    

    for i in range(N):

        for j in range(H+1):

            if j < A[i]:

                # 体力がマイナスなっても魔法は使用できる

                dp[i + 1][j] = min(dp[i][j], B[i])

            else:

                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])



    print((dp[N][H]))





if __name__ == "__main__":

    resolve()

def resolve():
    INF = 1 << 60
    H, N = list(map(int, input().split()))
    A, B = [], []
    for i in range(N):
        a, b = list(map(int, input().split()))
        A.append(a)
        B.append(b)
    dp = [[INF] * (H + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i + 1][min(j + A[i], H)] = min(
                dp[i + 1][min(j + A[i], H)], dp[i + 1][j] + B[i]
            )
    print((dp[N][H]))


if __name__ == "__main__":
    resolve()

def resolve():
    INF = 1 << 60
    H, N = list(map(int, input().split()))
    A, B = [], []
    for i in range(N):
        a, b = list(map(int, input().split()))
        A.append(a)
        B.append(b)
    dp = [[INF] * (H + 1) for _ in range(N + 1)]
    for i in range(N):
        dp[i][0] = 0
    for i in range(N):
        for j in range(H + 1):
            if j < A[i]:
                # 体力がマイナスなっても魔法は使用できる
                dp[i + 1][j] = min(dp[i][j], B[i])
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])
    print((dp[N][H]))


if __name__ == "__main__":
    resolve()

-    dp[0][0] = 0 +    for i in range(N): +        dp[i][0] = 0 -            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]) -            dp[i + 1][min(j + A[i], H)] = min( -                dp[i + 1][min(j + A[i], H)], dp[i + 1][j] + B[i] -            ) +            if j < A[i]: +                # 体力がマイナスなっても魔法は使用できる +                dp[i + 1][j] = min(dp[i][j], B[i]) +            else: +                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])