import numpy as np

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

ab = np.array([np.fromstring(eval(input()), dtype=np.int64, sep=" ") for _ in range(n)])



a = ab[:, 0]

b = ab[:, 1]



dp = np.zeros(10**6, dtype=np.int)



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

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



print((dp[h]))
import numpy as np

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

ab = np.array([np.fromstring(eval(input()), dtype=np.int64, sep=" ") for _ in range(n)])



a = ab[:, 0]

b = ab[:, 1]



dp = np.zeros(10**6, dtype=np.int)



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

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



print((dp[h]))
import numpy as np

h, n = list(map(int, input().split()))
ab = np.array([np.fromstring(eval(input()), dtype=np.int64, sep=" ") for _ in range(n)])
a = ab[:, 0]
b = ab[:, 1]
dp = np.zeros(10**6, dtype=np.int)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b)
print((dp[h]))

import numpy as np

h, n = list(map(int, input().split()))
ab = np.array([np.fromstring(eval(input()), dtype=np.int64, sep=" ") for _ in range(n)])
a = ab[:, 0]
b = ab[:, 1]
dp = np.zeros(10**6, dtype=np.int)
for i in range(1, h + 1):
    dp[i] = (dp[i - a] + b).min()
print((dp[h]))

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