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

s=[list(map(int, input().split())) for i in range(m)]

x=max(a for a,b in s)

dp=[0]*(n+x)

for i in range(0,n+x):

  if i>0:

    dp[i]=min(dp[i-a]+b for a,b in s)

print((min(dp[n:])))
import numpy as np



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

a=np.zeros(m,dtype=int)

b=np.zeros(m,dtype=int)

for i in range(m):

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

dp=np.zeros(10001,dtype=int)

for i in range(1,10001):

    dp[i]=(dp[i-a]+b).min()

print((dp[n]))
n, m = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(m)]
x = max(a for a, b in s)
dp = [0] * (n + x)
for i in range(0, n + x):
    if i > 0:
        dp[i] = min(dp[i - a] + b for a, b in s)
print((min(dp[n:])))

import numpy as np

n, m = list(map(int, input().split()))
a = np.zeros(m, dtype=int)
b = np.zeros(m, dtype=int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split()))
dp = np.zeros(10001, dtype=int)
for i in range(1, 10001):
    dp[i] = (dp[i - a] + b).min()
print((dp[n]))

+import numpy as np + -s = [list(map(int, input().split())) for i in range(m)] -x = max(a for a, b in s) -dp = [0] * (n + x) -for i in range(0, n + x): -    if i > 0: -        dp[i] = min(dp[i - a] + b for a, b in s) -print((min(dp[n:]))) +a = np.zeros(m, dtype=int) +b = np.zeros(m, dtype=int) +for i in range(m): +    a[i], b[i] = list(map(int, input().split())) +dp = np.zeros(10001, dtype=int) +for i in range(1, 10001): +    dp[i] = (dp[i - a] + b).min() +print((dp[n]))