import sys

import numpy as np



sr = lambda: sys.stdin.readline().rstrip()

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



H, N = lr()

U = 20000 # max(H)+max(A) これ以上は関係ない

INF = 10 ** 8

dp = np.full(U, INF, np.int64)

dp[0] = 0

for i in range(N):

    a, b = lr()

    n = (U + (-U)%a)

    #列のサイズはa

    dp = np.resize(dp, n).reshape(-1, a)

    dp -= (np.arange(n//a) * b)[:, None]

    dp = np.minimum.accumulate(dp, axis=0)

    dp += (np.arange(n//a) * b)[:, None]

    dp = np.ravel(dp)[:U]



print((min(dp[H:])))

#34
# coding: utf-8

import sys



sr = lambda: sys.stdin.readline().rstrip()

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



H, N = lr()

INF = 10 ** 15

limit = H + 100

dp = [INF] * limit

dp[0] = 0

for _ in range(N):

    a, b = lr()

    for i in range(limit):

        index = i+a

        if index > limit - 1:

            index = limit - 1

        dp[index] = min(dp[index], dp[i] + b)



dp = dp[H:]

answer = min(dp)

print(answer)

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
H, N = lr()
U = 20000  # max(H)+max(A) これ以上は関係ない
INF = 10**8
dp = np.full(U, INF, np.int64)
dp[0] = 0
for i in range(N):
    a, b = lr()
    n = U + (-U) % a
    # 列のサイズはa
    dp = np.resize(dp, n).reshape(-1, a)
    dp -= (np.arange(n // a) * b)[:, None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n // a) * b)[:, None]
    dp = np.ravel(dp)[:U]
print((min(dp[H:])))
# 34

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
H, N = lr()
INF = 10**15
limit = H + 100
dp = [INF] * limit
dp[0] = 0
for _ in range(N):
    a, b = lr()
    for i in range(limit):
        index = i + a
        if index > limit - 1:
            index = limit - 1
        dp[index] = min(dp[index], dp[i] + b)
dp = dp[H:]
answer = min(dp)
print(answer)

+# coding: utf-8 -import numpy as np -U = 20000  # max(H)+max(A) これ以上は関係ない -INF = 10**8 -dp = np.full(U, INF, np.int64) +INF = 10**15 +limit = H + 100 +dp = [INF] * limit -for i in range(N): +for _ in range(N): -    n = U + (-U) % a -    # 列のサイズはa -    dp = np.resize(dp, n).reshape(-1, a) -    dp -= (np.arange(n // a) * b)[:, None] -    dp = np.minimum.accumulate(dp, axis=0) -    dp += (np.arange(n // a) * b)[:, None] -    dp = np.ravel(dp)[:U] -print((min(dp[H:]))) -# 34 +    for i in range(limit): +        index = i + a +        if index > limit - 1: +            index = limit - 1 +        dp[index] = min(dp[index], dp[i] + b) +dp = dp[H:] +answer = min(dp) +print(answer)