# ダイナミック・プログラミング

# PythonではTLEを起こしてしまう例



INF = float('inf')



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

A = []

B = []



for i in range(N):

    a_i, b_i = list(map(int, input().split()))

    A.append(a_i)

    B.append(b_i)



dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列

dp[0][0] = 0 # 初期化処理

for i in range(0,N):

    for j in range(0,H+1):

        a, b = j+A[i], H

        min_h = a

        if a>b:

            min_h = b

        a, b = dp[i+1][j], dp[i][j]

        if a>b:

            dp[i+1][j] = b

        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]

        if a>b:

            dp[i+1][min_h] = b



print((dp[N][H]))

# Problem E - Crested Ibis vs Monster



# input

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

magic_list = []

for i in range(N):

    A, B = list(map(int, input().split()))

    magic_list.append([A, B])



# initialization

dp = [float('INF')]*(H+1)

dp[0] = 0

mg_len = len(magic_list)



# dp

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

    for j in range(mg_len):

        a = magic_list[j][0]

        b = magic_list[j][1]

        last_p = i - a

        if last_p<0:

            last_p = 0

        tmp = dp[last_p] + b

        dp[i] = min(dp[i], tmp)



# output

print((dp[H]))

# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例
INF = float("inf")
H, N = list(map(int, input().split()))
A = []
B = []
for i in range(N):
    a_i, b_i = list(map(int, input().split()))
    A.append(a_i)
    B.append(b_i)
dp = [[INF] * (H + 1) for i in range(N + 1)]  # DP用配列
dp[0][0] = 0  # 初期化処理
for i in range(0, N):
    for j in range(0, H + 1):
        a, b = j + A[i], H
        min_h = a
        if a > b:
            min_h = b
        a, b = dp[i + 1][j], dp[i][j]
        if a > b:
            dp[i + 1][j] = b
        a, b = dp[i + 1][min_h], dp[i + 1][j] + B[i]
        if a > b:
            dp[i + 1][min_h] = b
print((dp[N][H]))

# Problem E - Crested Ibis vs Monster
# input
H, N = list(map(int, input().split()))
magic_list = []
for i in range(N):
    A, B = list(map(int, input().split()))
    magic_list.append([A, B])
# initialization
dp = [float("INF")] * (H + 1)
dp[0] = 0
mg_len = len(magic_list)
# dp
for i in range(1, H + 1):
    for j in range(mg_len):
        a = magic_list[j][0]
        b = magic_list[j][1]
        last_p = i - a
        if last_p < 0:
            last_p = 0
        tmp = dp[last_p] + b
        dp[i] = min(dp[i], tmp)
# output
print((dp[H]))

-# ダイナミック・プログラミング -# PythonではTLEを起こしてしまう例 -INF = float("inf") +# Problem E - Crested Ibis vs Monster +# input -A = [] -B = [] +magic_list = [] -    a_i, b_i = list(map(int, input().split())) -    A.append(a_i) -    B.append(b_i) -dp = [[INF] * (H + 1) for i in range(N + 1)]  # DP用配列 -dp[0][0] = 0  # 初期化処理 -for i in range(0, N): -    for j in range(0, H + 1): -        a, b = j + A[i], H -        min_h = a -        if a > b: -            min_h = b -        a, b = dp[i + 1][j], dp[i][j] -        if a > b: -            dp[i + 1][j] = b -        a, b = dp[i + 1][min_h], dp[i + 1][j] + B[i] -        if a > b: -            dp[i + 1][min_h] = b -print((dp[N][H])) +    A, B = list(map(int, input().split())) +    magic_list.append([A, B]) +# initialization +dp = [float("INF")] * (H + 1) +dp[0] = 0 +mg_len = len(magic_list) +# dp +for i in range(1, H + 1): +    for j in range(mg_len): +        a = magic_list[j][0] +        b = magic_list[j][1] +        last_p = i - a +        if last_p < 0: +            last_p = 0 +        tmp = dp[last_p] + b +        dp[i] = min(dp[i], tmp) +# output +print((dp[H]))