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=[[1000000000]*(H+max(A)+1) for i in range(N+1)]





for i in range(N):

    DP[i+1][A[i]]=B[i]





for i in range(N):

    for h in range(H+max(A)+1):

        DP[i+1][h]=min(DP[i+1][h],DP[i][h])

        if h-A[i]>=0:

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



print((min(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=[1000000000]*(H+max(A)+1)

DP[0]=0





for i in range(N):

    DP[A[i]]=B[i]



for i in range(N):

    for h in range(A[i],H+max(A)+1):

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



print((min(DP[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 = [[1000000000] * (H + max(A) + 1) for i in range(N + 1)]
for i in range(N):
    DP[i + 1][A[i]] = B[i]
for i in range(N):
    for h in range(H + max(A) + 1):
        DP[i + 1][h] = min(DP[i + 1][h], DP[i][h])
        if h - A[i] >= 0:
            DP[i + 1][h] = min(DP[i + 1][h - A[i]] + B[i], DP[i + 1][h])
print((min(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 = [1000000000] * (H + max(A) + 1)
DP[0] = 0
for i in range(N):
    DP[A[i]] = B[i]
for i in range(N):
    for h in range(A[i], H + max(A) + 1):
        DP[h] = min(DP[h - A[i]] + B[i], DP[h])
print((min(DP[H:])))

-DP = [[1000000000] * (H + max(A) + 1) for i in range(N + 1)] +DP = [1000000000] * (H + max(A) + 1) +DP[0] = 0 -    DP[i + 1][A[i]] = B[i] +    DP[A[i]] = B[i] -    for h in range(H + max(A) + 1): -        DP[i + 1][h] = min(DP[i + 1][h], DP[i][h]) -        if h - A[i] >= 0: -            DP[i + 1][h] = min(DP[i + 1][h - A[i]] + B[i], DP[i + 1][h]) -print((min(DP[N][H:]))) +    for h in range(A[i], H + max(A) + 1): +        DP[h] = min(DP[h - A[i]] + B[i], DP[h]) +print((min(DP[H:])))