# E - Crested Ibis vs Monster

def main():

    INF = 1 << 30



    H, N, *AB = list(map(int, open(0).read().split()))

    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i

    dp[0] = 0

    for i in range(H):

        for a, b in zip(*[iter(AB)] * 2):

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

    print((min(dp[H:])))





if __name__ == "__main__":

    main()

# E - Crested Ibis vs Monster

def main():

    INF = 1 << 30



    H, N, *AB = list(map(int, open(0).read().split()))

    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i

    dp[0] = 0

    for a, b in zip(*[iter(AB)] * 2):

        for i in range(H):

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

    print((min(dp[H:])))





if __name__ == "__main__":

    main()

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (
        H + 10001
    )  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (
        H + 10001
    )  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()

-    for i in range(H): -        for a, b in zip(*[iter(AB)] * 2): +    for a, b in zip(*[iter(AB)] * 2): +        for i in range(H):