

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

a=[]

b=[]

for i in range(n):

    x,y=list(map(int,input().split()))

    a.append(x)

    b.append(y)



INF=float("inf")

    

dp=([[INF]*(1+h) for i in range(1+n)])





dp[0][0]=0



for i in range(n):

    # print(dp)

    for j in range(h+1):

        # print("i+1=",i+1,"j=",j)

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

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

        # print(i+1,j,min(h,j+a[i]),"\n",dp)

    # print("==================")



# print(dp)

print((dp[n][h]))

def LI():

  return list(map(int,input().split()))

h,n=LI()



a=[]

b=[]

for _ in range(n):

  x,y=LI()

  a.append(x)

  b.append(y)

  

INF=10**15

dp=[INF]*(h+max(a)+10)

dp[0]=0

for i in range(0,h+1):

  for j,k in zip(a,b):

    dp[i+j]=min(dp[i+j],dp[i]+k)



ans=INF

for i in dp[h:]:

  ans=min(ans,i)

print(ans)
h, n = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    x, y = list(map(int, input().split()))
    a.append(x)
    b.append(y)
INF = float("inf")
dp = [[INF] * (1 + h) for i in range(1 + n)]
dp[0][0] = 0
for i in range(n):
    # print(dp)
    for j in range(h + 1):
        # print("i+1=",i+1,"j=",j)
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][min(h, j + a[i])] = min(
            dp[i + 1][min(h, j + a[i])], dp[i + 1][j] + b[i]
        )
        # print(i+1,j,min(h,j+a[i]),"\n",dp)
    # print("==================")
# print(dp)
print((dp[n][h]))

def LI():
    return list(map(int, input().split()))


h, n = LI()
a = []
b = []
for _ in range(n):
    x, y = LI()
    a.append(x)
    b.append(y)
INF = 10**15
dp = [INF] * (h + max(a) + 10)
dp[0] = 0
for i in range(0, h + 1):
    for j, k in zip(a, b):
        dp[i + j] = min(dp[i + j], dp[i] + k)
ans = INF
for i in dp[h:]:
    ans = min(ans, i)
print(ans)

-h, n = list(map(int, input().split())) +def LI(): +    return list(map(int, input().split())) + + +h, n = LI() -for i in range(n): -    x, y = list(map(int, input().split())) +for _ in range(n): +    x, y = LI() -INF = float("inf") -dp = [[INF] * (1 + h) for i in range(1 + n)] -dp[0][0] = 0 -for i in range(n): -    # print(dp) -    for j in range(h + 1): -        # print("i+1=",i+1,"j=",j) -        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]) -        dp[i + 1][min(h, j + a[i])] = min( -            dp[i + 1][min(h, j + a[i])], dp[i + 1][j] + b[i] -        ) -        # print(i+1,j,min(h,j+a[i]),"\n",dp) -    # print("==================") -# print(dp) -print((dp[n][h])) +INF = 10**15 +dp = [INF] * (h + max(a) + 10) +dp[0] = 0 +for i in range(0, h + 1): +    for j, k in zip(a, b): +        dp[i + j] = min(dp[i + j], dp[i] + k) +ans = INF +for i in dp[h:]: +    ans = min(ans, i) +print(ans)