h,n = list(map(int,input().split()))

aa = [0]*n

bb = [0]*n

for i in range(n):

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

    aa[i] = a

    bb[i] = b

m = max(aa)



dp = [float("inf") for _ in range(h+m)]

dp[0] = 0

for i in range(1,h+m):

    for j in range(n):

        if i-aa[j] >= 0:

            dp[i] = min(dp[i-aa[j]]+bb[j],dp[i])



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()))

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

dp[0] = 0

for i in range(h):

    for j in range(n):

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

print((dp[h]))
h, n = list(map(int, input().split()))
aa = [0] * n
bb = [0] * n
for i in range(n):
    a, b = list(map(int, input().split()))
    aa[i] = a
    bb[i] = b
m = max(aa)
dp = [float("inf") for _ in range(h + m)]
dp[0] = 0
for i in range(1, h + m):
    for j in range(n):
        if i - aa[j] >= 0:
            dp[i] = min(dp[i - aa[j]] + bb[j], dp[i])
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()))
dp = [10**9] * (h + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[min(i + a[j], h)] = min(dp[min(i + a[j], h)], dp[i] + b[j])
print((dp[h]))

-aa = [0] * n -bb = [0] * n +a = [0] * n +b = [0] * n -    a, b = list(map(int, input().split())) -    aa[i] = a -    bb[i] = b -m = max(aa) -dp = [float("inf") for _ in range(h + m)] +    a[i], b[i] = list(map(int, input().split())) +dp = [10**9] * (h + 1) -for i in range(1, h + m): +for i in range(h): -        if i - aa[j] >= 0: -            dp[i] = min(dp[i - aa[j]] + bb[j], dp[i]) -print((min(dp[h:]))) +        dp[min(i + a[j], h)] = min(dp[min(i + a[j], h)], dp[i] + b[j]) +print((dp[h]))