hh,n = list(map(int,input().split(' ')))

spells = [list(map(int, input().split(' '))) for _ in range(n)]

h = {}

h[0] = 0



#h[health] = cost in points

for health in range(1, hh+1):

	for u,v in spells:

		h[health] = min(h[health] if health in h else +float('inf'), h[max(0,health - u)] + v)



print(h[hh])
hh,n = list(map(int,input().split(' ')))

spells = [list(map(int, input().split(' '))) for _ in range(n)]

h = [+float('inf')] * (hh+1)

h[0] = 0

for health in range(1, hh+1):

	for u,v in spells: h[health] = min(h[health], h[max(0,health - u)] + v)



print(h[hh])
hh, n = list(map(int, input().split(" ")))
spells = [list(map(int, input().split(" "))) for _ in range(n)]
h = {}
h[0] = 0
# h[health] = cost in points
for health in range(1, hh + 1):
    for u, v in spells:
        h[health] = min(
            h[health] if health in h else +float("inf"), h[max(0, health - u)] + v
        )
print(h[hh])

hh, n = list(map(int, input().split(" ")))
spells = [list(map(int, input().split(" "))) for _ in range(n)]
h = [+float("inf")] * (hh + 1)
h[0] = 0
for health in range(1, hh + 1):
    for u, v in spells:
        h[health] = min(h[health], h[max(0, health - u)] + v)
print(h[hh])

-h = {} +h = [+float("inf")] * (hh + 1) -# h[health] = cost in points -        h[health] = min( -            h[health] if health in h else +float("inf"), h[max(0, health - u)] + v -        ) +        h[health] = min(h[health], h[max(0, health - u)] + v)