import sys

input = sys.stdin.buffer.readline

 

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

AB = [list(map(int, input().split())) for _ in range(n)]



inf=float("inf")

dp=[inf]*(h+1)

 

dp[0]=0



for a,b in AB:

    for i in range(h):

        if dp[i]!=float("inf"):

            dp[min(i+a,h)]=min(dp[min(i+a,h)],dp[i]+b)

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

 

Ama = max(A)

 

dp=[float("inf")]*(h+Ama+1)

dp[0]=0

 

for i in range(h+1):

    for j in range(n):

        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

print((min(dp[h:])))
import sys

input = sys.stdin.buffer.readline
h, n = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(n)]
inf = float("inf")
dp = [inf] * (h + 1)
dp[0] = 0
for a, b in AB:
    for i in range(h):
        if dp[i] != float("inf"):
            dp[min(i + a, h)] = min(dp[min(i + a, h)], dp[i] + b)
print((dp[-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)
Ama = max(A)
dp = [float("inf")] * (h + Ama + 1)
dp[0] = 0
for i in range(h + 1):
    for j in range(n):
        dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j])
print((min(dp[h:])))

-import sys - -input = sys.stdin.buffer.readline -AB = [list(map(int, input().split())) for _ in range(n)] -inf = float("inf") -dp = [inf] * (h + 1) +A = [] +B = [] +for i in range(n): +    a, b = list(map(int, input().split())) +    A.append(a) +    B.append(b) +Ama = max(A) +dp = [float("inf")] * (h + Ama + 1) -for a, b in AB: -    for i in range(h): -        if dp[i] != float("inf"): -            dp[min(i + a, h)] = min(dp[min(i + a, h)], dp[i] + b) -print((dp[-1])) +for i in range(h + 1): +    for j in range(n): +        dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j]) +print((min(dp[h:])))