h, n = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(n)]



dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]

for i in range(n + 1):

    dp[i][0] = 0



for i in range(1, n + 1):

    for j in range(1, h + 1):

        a, b = ab[i-1]

        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)



ans = dp[n][h]

print(ans)

h, n = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(n)]



dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]

for i in range(n + 1):

    dp[i][0] = 0



for i, (a, b) in enumerate(ab, 1):

    for j in range(h + 1):

        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)



ans = dp[n][h]

print(ans)

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(1, n + 1):
    for j in range(1, h + 1):
        a, b = ab[i - 1]
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - a, 0)] + b)
ans = dp[n][h]
print(ans)

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i, (a, b) in enumerate(ab, 1):
    for j in range(h + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - a, 0)] + b)
ans = dp[n][h]
print(ans)

-for i in range(1, n + 1): -    for j in range(1, h + 1): -        a, b = ab[i - 1] +for i, (a, b) in enumerate(ab, 1): +    for j in range(h + 1):