import numpy as np



H, N = list(map(int, input().split()))

AB = np.array([list(map(int, input().split())) for i in range(N)])

A = AB[:, 0]

B = AB[:, 1]



# インデックスはライフ 値はそれを以下にする最小MP

# dp = np.array([0 for i in range(H+1)])

# dp = np.array([10**10 for i in range(H+1)])

dp = np.array([np.inf for i in range(H+1)])

dp[0] = 0



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

    dp[i] = min(dp[np.maximum(i-A, 0)] + B)



print((int(dp[-1])))
import numpy as np



H, N = list(map(int, input().split()))

AB = np.array([list(map(int, input().split())) for i in range(N)])

A = AB[:, 0]

B = AB[:, 1]



# インデックスはライフ 値はそれを以下にする最小MP

dp = np.array([0 for i in range(H+1)])



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

    dp[i] = min(dp[np.maximum(i - A, 0)] + B)



print((int(dp[-1])))
import numpy as np

H, N = list(map(int, input().split()))
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]
# インデックスはライフ 値はそれを以下にする最小MP
# dp = np.array([0 for i in range(H+1)])
# dp = np.array([10**10 for i in range(H+1)])
dp = np.array([np.inf for i in range(H + 1)])
dp[0] = 0
for i in range(1, H + 1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)
print((int(dp[-1])))

import numpy as np

H, N = list(map(int, input().split()))
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]
# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([0 for i in range(H + 1)])
for i in range(1, H + 1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)
print((int(dp[-1])))

-# dp = np.array([0 for i in range(H+1)]) -# dp = np.array([10**10 for i in range(H+1)]) -dp = np.array([np.inf for i in range(H + 1)]) -dp[0] = 0 +dp = np.array([0 for i in range(H + 1)])