import sys





def resolve():

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

    m = list(map(int, sys.stdin.read().split()))

    AB = list(zip(m, m))

    INF = 10**20

    dp = [INF]*(H+10**4)

    dp[0] = 0

    for a, b in AB:

        for j in range(H+10**4):

            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)

    return min(dp[H:])





if __name__ == '__main__':

    print((resolve()))

import sys

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

m = list(map(int, sys.stdin.read().split()))

AB = list(zip(m, m))

INF = 10**20

dp = [INF]*(H+10**4)

dp[0] = 0

for a, b in AB:

    for j in range(H+10**4):

        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)

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

import sys


def resolve():
    H, N = list(map(int, sys.stdin.readline().split()))
    m = list(map(int, sys.stdin.read().split()))
    AB = list(zip(m, m))
    INF = 10**20
    dp = [INF] * (H + 10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H + 10**4):
            dp[j] = min(dp[j], dp[j - a] + b if j - a >= 0 else INF)
    return min(dp[H:])


if __name__ == "__main__":
    print((resolve()))

import sys

H, N = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.read().split()))
AB = list(zip(m, m))
INF = 10**20
dp = [INF] * (H + 10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H + 10**4):
        dp[j] = min(dp[j], dp[j - a] + b if j - a >= 0 else INF)
print((min(dp[H:])))

- -def resolve(): -    H, N = list(map(int, sys.stdin.readline().split())) -    m = list(map(int, sys.stdin.read().split())) -    AB = list(zip(m, m)) -    INF = 10**20 -    dp = [INF] * (H + 10**4) -    dp[0] = 0 -    for a, b in AB: -        for j in range(H + 10**4): -            dp[j] = min(dp[j], dp[j - a] + b if j - a >= 0 else INF) -    return min(dp[H:]) - - -if __name__ == "__main__": -    print((resolve())) +H, N = list(map(int, sys.stdin.readline().split())) +m = list(map(int, sys.stdin.read().split())) +AB = list(zip(m, m)) +INF = 10**20 +dp = [INF] * (H + 10**4) +dp[0] = 0 +for a, b in AB: +    for j in range(H + 10**4): +        dp[j] = min(dp[j], dp[j - a] + b if j - a >= 0 else INF) +print((min(dp[H:])))