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

abl = []

for _ in range(N):

    ab = list(map(int, input().split()) )

    abl.append(ab)



dp = [10**8]*(2*10**4+1)

dp[0] = 0

for h in range(H+1):

    for ab in abl:

        a,b = ab

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



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

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



dp = [10**18]*(h+1)

dp[0] = 0

for i in range(h):

    for a,b in abl:

        next_h = min(h,i+a)

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



print((dp[-1]))
H, N = list(map(int, input().split()))
abl = []
for _ in range(N):
    ab = list(map(int, input().split()))
    abl.append(ab)
dp = [10**8] * (2 * 10**4 + 1)
dp[0] = 0
for h in range(H + 1):
    for ab in abl:
        a, b = ab
        dp[h + a] = min(dp[h + a], dp[h] + b)
print((min(dp[H:])))

h, n = list(map(int, input().split()))
abl = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10**18] * (h + 1)
dp[0] = 0
for i in range(h):
    for a, b in abl:
        next_h = min(h, i + a)
        dp[next_h] = min(dp[next_h], dp[i] + b)
print((dp[-1]))

-H, N = list(map(int, input().split())) -abl = [] -for _ in range(N): -    ab = list(map(int, input().split())) -    abl.append(ab) -dp = [10**8] * (2 * 10**4 + 1) +h, n = list(map(int, input().split())) +abl = [tuple(map(int, input().split())) for _ in range(n)] +dp = [10**18] * (h + 1) -for h in range(H + 1): -    for ab in abl: -        a, b = ab -        dp[h + a] = min(dp[h + a], dp[h] + b) -print((min(dp[H:]))) +for i in range(h): +    for a, b in abl: +        next_h = min(h, i + a) +        dp[next_h] = min(dp[next_h], dp[i] + b) +print((dp[-1]))