w, h = (int(x) for x in input().split())

ab = []

for _ in range(h):

    a, b = (int(x) for x in input().split())

    ab.append([a, b])



dp = [0] * (w + max(a for a, b in ab))



for j in range(1, w+1):

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



print((dp[w]))
w, h = (int(x) for x in input().split())

ab = []

for _ in range(h):

    a, b = (int(x) for x in input().split())

    ab.append([a, b])

 

dp = [10000000000000 for i in range(w+1)]

 

for j in range(w+1):

    for i in range(h):

        if j <= ab[i][0]:

            dp[j] = min(dp[j], ab[i][1])

        else:

            dp[j] = min(dp[j], dp[j-ab[i][0]]+ab[i][1])

 

print((dp[w]))
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [0] * (w + max(a for a, b in ab))
for j in range(1, w + 1):
    dp[j] = min(dp[j - a] + b for a, b in ab)
print((dp[w]))

w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [10000000000000 for i in range(w + 1)]
for j in range(w + 1):
    for i in range(h):
        if j <= ab[i][0]:
            dp[j] = min(dp[j], ab[i][1])
        else:
            dp[j] = min(dp[j], dp[j - ab[i][0]] + ab[i][1])
print((dp[w]))

-dp = [0] * (w + max(a for a, b in ab)) -for j in range(1, w + 1): -    dp[j] = min(dp[j - a] + b for a, b in ab) +dp = [10000000000000 for i in range(w + 1)] +for j in range(w + 1): +    for i in range(h): +        if j <= ab[i][0]: +            dp[j] = min(dp[j], ab[i][1]) +        else: +            dp[j] = min(dp[j], dp[j - ab[i][0]] + ab[i][1])