def chmin(dp, i, *x):

  dp[i] = min(dp[i], *x)

INF = float("inf")



# dp[i] := min 消耗する魔力 to H -= i

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

dp = [0] + [INF]*h

for _ in [None]*n:

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

  for j in range(h + 1):

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

print((dp[h]))
(h,n),*t=[list(map(int,o.split()))for o in open(0)]

d=[0]+[9e9]*h

for a,b in t:

 for j in range(h+1):d[j]=min(d[j],d[max(0,j-a)]+b)

print((d[h]))
def chmin(dp, i, *x):
    dp[i] = min(dp[i], *x)


INF = float("inf")
# dp[i] := min 消耗する魔力 to H -= i
h, n = list(map(int, input().split()))
dp = [0] + [INF] * h
for _ in [None] * n:
    a, b = list(map(int, input().split()))
    for j in range(h + 1):
        chmin(dp, min(j + a, h), dp[j] + b)
print((dp[h]))

(h, n), *t = [list(map(int, o.split())) for o in open(0)]
d = [0] + [9e9] * h
for a, b in t:
    for j in range(h + 1):
        d[j] = min(d[j], d[max(0, j - a)] + b)
print((d[h]))

-def chmin(dp, i, *x): -    dp[i] = min(dp[i], *x) - - -INF = float("inf") -# dp[i] := min 消耗する魔力 to H -= i -h, n = list(map(int, input().split())) -dp = [0] + [INF] * h -for _ in [None] * n: -    a, b = list(map(int, input().split())) +(h, n), *t = [list(map(int, o.split())) for o in open(0)] +d = [0] + [9e9] * h +for a, b in t: -        chmin(dp, min(j + a, h), dp[j] + b) -print((dp[h])) +        d[j] = min(d[j], d[max(0, j - a)] + b) +print((d[h]))