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



INF=10**9

dp=[INF]*(H+1)

# dp[x]:xダメージを与えるための最小魔力

dp[0]=0

for i in range(N):

  for j in range(len(dp)):

    if dp[j]!=INF:

      if j+A[i]<len(dp):

        if dp[j+A[i]]>dp[j]+B[i]:

          dp[j+A[i]]=dp[j]+B[i]

      else:

        if dp[len(dp)-1]>dp[j]+B[i]:

          dp[len(dp)-1]=dp[j]+B[i]

print((dp[-1]))
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()))



INF=10**9

dp=[INF]*(H+max(A))

# dp[x]:xダメージを与えるための最小魔力

dp[0]=0

for i in range(N):

  for j in range(H):

    if dp[j]!=INF:

      if dp[j+A[i]]>dp[j]+B[i]:

        dp[j+A[i]]=dp[j]+B[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()))
INF = 10**9
dp = [INF] * (H + 1)
# dp[x]:xダメージを与えるための最小魔力
dp[0] = 0
for i in range(N):
    for j in range(len(dp)):
        if dp[j] != INF:
            if j + A[i] < len(dp):
                if dp[j + A[i]] > dp[j] + B[i]:
                    dp[j + A[i]] = dp[j] + B[i]
            else:
                if dp[len(dp) - 1] > dp[j] + B[i]:
                    dp[len(dp) - 1] = dp[j] + B[i]
print((dp[-1]))

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()))
INF = 10**9
dp = [INF] * (H + max(A))
# dp[x]:xダメージを与えるための最小魔力
dp[0] = 0
for i in range(N):
    for j in range(H):
        if dp[j] != INF:
            if dp[j + A[i]] > dp[j] + B[i]:
                dp[j + A[i]] = dp[j] + B[i]
print((min(dp[H:])))

-dp = [INF] * (H + 1) +dp = [INF] * (H + max(A)) -    for j in range(len(dp)): +    for j in range(H): -            if j + A[i] < len(dp): -                if dp[j + A[i]] > dp[j] + B[i]: -                    dp[j + A[i]] = dp[j] + B[i] -            else: -                if dp[len(dp) - 1] > dp[j] + B[i]: -                    dp[len(dp) - 1] = dp[j] + B[i] -print((dp[-1])) +            if dp[j + A[i]] > dp[j] + B[i]: +                dp[j + A[i]] = dp[j] + B[i] +print((min(dp[H:])))