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

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

dp = [float('inf')] * (H + 1)

dp[0] = 0

for h in range(H):

    if dp[h] == float('inf'):

        continue

    for a, b in M:

        idx = min(H, h + a)

        dp[idx] = min(dp[idx], dp[h] + b)

print((dp[H]))

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

dp = [10 ** 9] * (H + 1)

dp[0] = 0

for _ in range(N):

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

    for i in range(H):

        idx = min(H, i + a)

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

print((dp[H]))



H, N = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for _ in range(N)]
dp = [float("inf")] * (H + 1)
dp[0] = 0
for h in range(H):
    if dp[h] == float("inf"):
        continue
    for a, b in M:
        idx = min(H, h + a)
        dp[idx] = min(dp[idx], dp[h] + b)
print((dp[H]))

H, N = list(map(int, input().split()))
dp = [10**9] * (H + 1)
dp[0] = 0
for _ in range(N):
    a, b = list(map(int, input().split()))
    for i in range(H):
        idx = min(H, i + a)
        dp[idx] = min(dp[idx], dp[i] + b)
print((dp[H]))

-M = [tuple(map(int, input().split())) for _ in range(N)] -dp = [float("inf")] * (H + 1) +dp = [10**9] * (H + 1) -for h in range(H): -    if dp[h] == float("inf"): -        continue -    for a, b in M: -        idx = min(H, h + a) -        dp[idx] = min(dp[idx], dp[h] + b) +for _ in range(N): +    a, b = list(map(int, input().split())) +    for i in range(H): +        idx = min(H, i + a) +        dp[idx] = min(dp[idx], dp[i] + b)