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

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

dp = [10**10]*(10**5)

dp[0] = 0

for e in M:

    for k in range(e[0],10**5):

        dp[k] = min(dp[k],dp[k-e[0]]+e[1])

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

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

M = []

for k in range(N):

    M.append(list(map(int,input().split())))

dp = [10**9]*(10**5)

dp[0] = 0

for A, B in M:

    for k in range(A+1):

        dp[k] = min(dp[k],B)

    for k in range(A+1,H+1):

        dp[k] = min(dp[k],dp[k-A]+B)

print((dp[H]))

H, N = list(map(int, input().split()))
M = [list(map(int, input().split())) for k in range(N)]
dp = [10**10] * (10**5)
dp[0] = 0
for e in M:
    for k in range(e[0], 10**5):
        dp[k] = min(dp[k], dp[k - e[0]] + e[1])
print((min(dp[H:])))

H, N = list(map(int, input().split()))
M = []
for k in range(N):
    M.append(list(map(int, input().split())))
dp = [10**9] * (10**5)
dp[0] = 0
for A, B in M:
    for k in range(A + 1):
        dp[k] = min(dp[k], B)
    for k in range(A + 1, H + 1):
        dp[k] = min(dp[k], dp[k - A] + B)
print((dp[H]))

-M = [list(map(int, input().split())) for k in range(N)] -dp = [10**10] * (10**5) +M = [] +for k in range(N): +    M.append(list(map(int, input().split()))) +dp = [10**9] * (10**5) -for e in M: -    for k in range(e[0], 10**5): -        dp[k] = min(dp[k], dp[k - e[0]] + e[1]) -print((min(dp[H:]))) +for A, B in M: +    for k in range(A + 1): +        dp[k] = min(dp[k], B) +    for k in range(A + 1, H + 1): +        dp[k] = min(dp[k], dp[k - A] + B) +print((dp[H]))