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[i+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト

dp=[[float("inf")]*(H+1) for _ in range(N+1)]



for i in range(N):

	for h in range(H+1):

		if A[i]>=h:

			dp[i+1][h] = min(dp[i][h], B[i])

		else:

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

print((dp[-1][-1]))
H, N = list(map(int, input().split()))



A=[]

B=[]

for _ in range(N):

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

	A.append(a)

	B.append(b)



dp=[[float("inf")]*(H+1) for _ in range(N+1)]

dp[0][0]=0

for i in range(N):

	a, b = A[i], B[i]

	for j in range(H+1):

		if a>=j:

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

		else:

			dp[i+1][j] = min(dp[i][j], dp[i+1][j-a]+b)

print((dp[-1][-1]))

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[i+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト
dp = [[float("inf")] * (H + 1) for _ in range(N + 1)]
for i in range(N):
    for h in range(H + 1):
        if A[i] >= h:
            dp[i + 1][h] = min(dp[i][h], B[i])
        else:
            dp[i + 1][h] = min(
                dp[i][h], dp[i + 1][h - A[i]] + B[i], dp[i][h - A[i]] + B[i]
            )
print((dp[-1][-1]))

H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
dp = [[float("inf")] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    a, b = A[i], B[i]
    for j in range(H + 1):
        if a >= j:
            dp[i + 1][j] = min(dp[i][j], b)
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b)
print((dp[-1][-1]))

-for i in range(N): +for _ in range(N): -# dp[i+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト +dp[0][0] = 0 -    for h in range(H + 1): -        if A[i] >= h: -            dp[i + 1][h] = min(dp[i][h], B[i]) +    a, b = A[i], B[i] +    for j in range(H + 1): +        if a >= j: +            dp[i + 1][j] = min(dp[i][j], b) -            dp[i + 1][h] = min( -                dp[i][h], dp[i + 1][h - A[i]] + B[i], dp[i][h - A[i]] + B[i] -            ) +            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b)