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

A = [0]*N

B = [0]*N



for i in range(N):

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



#i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)

dp = [[float("inf")]*(H+1) for _ in range(N+1)]

dp[0][0] = 0



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

    for j in range(H+1):

        if j < A[i-1]:

            dp[i][j] = min(dp[i-1][j], B[i-1])

        else:

            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])



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


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

A = [0]*N

B = [0]*N



for i in range(N):

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

"""

# i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)

dp = [[float("inf")]*(H+1) for _ in range(N+1)]

dp[0][0] = 0



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

    for j in range(H+1):

        if j < A[i-1]:

            dp[i][j] = min(dp[i-1][j], B[i-1])

        else:

            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])



print(dp[N][H])

"""

# メモリ削減(ただし, 計算時間は増えてしまう)

# 配るDPで考える

# モンスターの体力をj減らすのに必要な魔力の最小値

dp = [float("inf")]*(H+10**4)

dp[0] = 0

for i in range(N):

    for j in range(H):

        dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])



ans = float("inf")

for j in range(H, H+10**4):

    ans = min(ans, dp[j])



print(ans)

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
# i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(H + 1):
        if j < A[i - 1]:
            dp[i][j] = min(dp[i - 1][j], B[i - 1])
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - A[i - 1]] + B[i - 1])
print((dp[N][H]))

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))
"""
# i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(H+1):
        if j < A[i-1]:
            dp[i][j] = min(dp[i-1][j], B[i-1])
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])
print(dp[N][H])
"""
# メモリ削減(ただし, 計算時間は増えてしまう)
# 配るDPで考える
# モンスターの体力をj減らすのに必要な魔力の最小値
dp = [float("inf")] * (H + 10**4)
dp[0] = 0
for i in range(N):
    for j in range(H):
        dp[j + A[i]] = min(dp[j + A[i]], dp[j] + B[i])
ans = float("inf")
for j in range(H, H + 10**4):
    ans = min(ans, dp[j])
print(ans)

+""" -dp = [[float("inf")] * (H + 1) for _ in range(N + 1)] +dp = [[float("inf")]*(H+1) for _ in range(N+1)] -for i in range(1, N + 1): -    for j in range(H + 1): -        if j < A[i - 1]: -            dp[i][j] = min(dp[i - 1][j], B[i - 1]) +for i in range(1, N+1): +    for j in range(H+1): +        if j < A[i-1]: +            dp[i][j] = min(dp[i-1][j], B[i-1]) -            dp[i][j] = min(dp[i - 1][j], dp[i][j - A[i - 1]] + B[i - 1]) -print((dp[N][H])) +            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1]) +print(dp[N][H]) +""" +# メモリ削減(ただし, 計算時間は増えてしまう) +# 配るDPで考える +# モンスターの体力をj減らすのに必要な魔力の最小値 +dp = [float("inf")] * (H + 10**4) +dp[0] = 0 +for i in range(N): +    for j in range(H): +        dp[j + A[i]] = min(dp[j + A[i]], dp[j] + B[i]) +ans = float("inf") +for j in range(H, H + 10**4): +    ans = min(ans, dp[j]) +print(ans)