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



A, B = [0] * N, [0] * N

for i in range(N):

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



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



dp[0][0] = 0



for i in range(N):

    for j in range(H+1):

        nj = min(j+A[i], H)



        dp[i+1][nj] = min(dp[i][nj], dp[i+1][j] + B[i])



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



A, B = [0] * N, [0] * N



for i in range(N):

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



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

dp[0] = 0



for i in range(N):

    for j in range(H+1):

        nj = min(j+A[i], H)

        dp[nj] = min(dp[nj], dp[j]+B[i])

print((dp[H]))
H, N = list(map(int, input().split()))
A, B = [0] * N, [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
dp = [[10**9] * (H + 1)] * (N + 1)
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        nj = min(j + A[i], H)
        dp[i + 1][nj] = min(dp[i][nj], dp[i + 1][j] + B[i])
print((dp[N][H]))

H, N = list(map(int, input().split()))
A, B = [0] * N, [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(N):
    for j in range(H + 1):
        nj = min(j + A[i], H)
        dp[nj] = min(dp[nj], dp[j] + B[i])
print((dp[H]))

-dp = [[10**9] * (H + 1)] * (N + 1) -dp[0][0] = 0 +dp = [10**9] * (H + 1) +dp[0] = 0 -        dp[i + 1][nj] = min(dp[i][nj], dp[i + 1][j] + B[i]) -print((dp[N][H])) +        dp[nj] = min(dp[nj], dp[j] + B[i]) +print((dp[H]))