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

A = [0] * N

B = [0] * N

for i in range(N):

    A[i], B[i] = list(map(int, input().split()))

ma = max(A)

dp = [float("inf")] * (H + ma)

dp[0] = 0

for i in range(N):

    a = A[i]

    b = B[i]

    for j in range(1, H + ma):

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

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



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

A = [0] * N

B = [0] * N

for i in range(N):

    A[i], B[i] = list(map(int, input().split()))

ma = max(A)

dp = [0] * (H + ma)

dp[0] = 0

for i in range(N):

    a = A[i]

    b = B[i]

    for j in range(1, H + ma):

        if dp[j] == 0:

            dp[j] = dp[j - a] + b

        else:

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

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

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print((min(dp[H:])))

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
print((min(dp[H:])))

-dp = [float("inf")] * (H + ma) +dp = [0] * (H + ma) -        dp[j] = min(dp[j - a] + b, dp[j]) +        if dp[j] == 0: +            dp[j] = dp[j - a] + b +        else: +            dp[j] = min(dp[j - a] + b, dp[j])