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

magics = []

for _ in range(N):

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

  magics.append([a, b])

max_a = max(a for a, _ in magics)

dp = [0]*(H+max_a)

for i in range(1, H+max_a):

  dp[i] = min(dp[i-a]+b for a, b in magics)

print((min(dp[H:])))
H, N = list(map(int, input().split()))

magics = [tuple(map(int, input().split())) for _ in range(N)]

maxA = max([x for x, y in magics])



dp = [10**18]*(H+maxA+1)

dp[0] = 0



for i in range(1, H+maxA+1):

    for j in range(N):

        a, b = magics[j]

        if a<=i:

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



print((min(dp[H:])))
H, N = list(map(int, input().split()))
magics = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    magics.append([a, b])
max_a = max(a for a, _ in magics)
dp = [0] * (H + max_a)
for i in range(1, H + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print((min(dp[H:])))

H, N = list(map(int, input().split()))
magics = [tuple(map(int, input().split())) for _ in range(N)]
maxA = max([x for x, y in magics])
dp = [10**18] * (H + maxA + 1)
dp[0] = 0
for i in range(1, H + maxA + 1):
    for j in range(N):
        a, b = magics[j]
        if a <= i:
            dp[i] = min(dp[i - a] + b, dp[i])
print((min(dp[H:])))

-magics = [] -for _ in range(N): -    a, b = list(map(int, input().split())) -    magics.append([a, b]) -max_a = max(a for a, _ in magics) -dp = [0] * (H + max_a) -for i in range(1, H + max_a): -    dp[i] = min(dp[i - a] + b for a, b in magics) +magics = [tuple(map(int, input().split())) for _ in range(N)] +maxA = max([x for x, y in magics]) +dp = [10**18] * (H + maxA + 1) +dp[0] = 0 +for i in range(1, H + maxA + 1): +    for j in range(N): +        a, b = magics[j] +        if a <= i: +            dp[i] = min(dp[i - a] + b, dp[i])