H,N=list(map(int,input().split()))

A=[]

B=[]

for i in range(N):

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

   A.append(a)

   B.append(b)



DP=[[0]*(H+max(A)) for i in range(N)]

DP.insert(0,[10**8+1]*(H+max(A)))

DP[0][0]=0



for i in range(1,N+1):

   for j in range(1,H+max(A)):

      if j-A[i-1]>0:

         DP[i][j]=min(DP[i-1][j],DP[i][j-A[i-1]]+B[i-1])

      else:

         DP[i][j]=min(DP[i-1][j],B[i-1])



print((DP[N][H]))
H,N=list(map(int,input().split()))

A=[]

B=[]

for i in range(N):

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

   A.append(a)

   B.append(b)



DP=[[0]*(H+max(A)) for i in range(N)]

DP.insert(0,[10**8+1]*(H+max(A)))

DP[0][0]=0



for i in range(1,N+1):

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

      if j-A[i-1]>0:

         DP[i][j]=min(DP[i-1][j],DP[i][j-A[i-1]]+B[i-1])

      else:

         DP[i][j]=min(DP[i-1][j],B[i-1])



print((DP[N][H]))
H, N = list(map(int, input().split()))
A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
DP = [[0] * (H + max(A)) for i in range(N)]
DP.insert(0, [10**8 + 1] * (H + max(A)))
DP[0][0] = 0
for i in range(1, N + 1):
    for j in range(1, H + max(A)):
        if j - A[i - 1] > 0:
            DP[i][j] = min(DP[i - 1][j], DP[i][j - A[i - 1]] + B[i - 1])
        else:
            DP[i][j] = min(DP[i - 1][j], B[i - 1])
print((DP[N][H]))

H, N = list(map(int, input().split()))
A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
DP = [[0] * (H + max(A)) for i in range(N)]
DP.insert(0, [10**8 + 1] * (H + max(A)))
DP[0][0] = 0
for i in range(1, N + 1):
    for j in range(1, H + 1):
        if j - A[i - 1] > 0:
            DP[i][j] = min(DP[i - 1][j], DP[i][j - A[i - 1]] + B[i - 1])
        else:
            DP[i][j] = min(DP[i - 1][j], B[i - 1])
print((DP[N][H]))

-    for j in range(1, H + max(A)): +    for j in range(1, H + 1):