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

AB=[]

maA=0

inf=float("inf")

for i in range(n):

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

   maA=max(maA,a)

   AB.append((a,b))



dp=[inf]*(h+maA+1)

dp[0]=0

for i in range(h+1):

   for aj,bj in AB:

      dp[i+aj]=min(dp[i+aj],dp[i]+bj)

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

L=[]

maA=0

inf=float("inf")

for i in range(n):

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

      L.append((a,b))

      maA=max(maA,a)



dp=[inf]*(h+maA+1)

dp[0]=0

for i in range(h):

      for j in L:

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

      

print((min(dp[h:])))   
h, n = list(map(int, input().split()))
AB = []
maA = 0
inf = float("inf")
for i in range(n):
    a, b = list(map(int, input().split()))
    maA = max(maA, a)
    AB.append((a, b))
dp = [inf] * (h + maA + 1)
dp[0] = 0
for i in range(h + 1):
    for aj, bj in AB:
        dp[i + aj] = min(dp[i + aj], dp[i] + bj)
print((min(dp[h:])))

h, n = list(map(int, input().split()))
L = []
maA = 0
inf = float("inf")
for i in range(n):
    a, b = list(map(int, input().split()))
    L.append((a, b))
    maA = max(maA, a)
dp = [inf] * (h + maA + 1)
dp[0] = 0
for i in range(h):
    for j in L:
        dp[i + j[0]] = min(dp[i + j[0]], dp[i] + j[1])
print((min(dp[h:])))

-AB = [] +L = [] +    L.append((a, b)) -    AB.append((a, b)) -for i in range(h + 1): -    for aj, bj in AB: -        dp[i + aj] = min(dp[i + aj], dp[i] + bj) +for i in range(h): +    for j in L: +        dp[i + j[0]] = min(dp[i + j[0]], dp[i] + j[1])