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

ab = [list(map(int, input().split())) for _ in range(n)]

max_a = 0 

for a, b in ab:

  max_a = max(max_a, a)

# i番目まで見たときに、モンスターの体力をj減らした時の、トキの消耗した魔力の最小値

dp = [[float('inf')]*(h+max_a+1) for _ in range(n+1)]

for i in range(n+1):

  dp[i][0] = 0

for i in range(n):

  a, b = ab[i]

  for j in range(h+max_a+1):

    if j-a >= 0:

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

    else:

      dp[i+1][j] = dp[i][j]





ans = float('inf')

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

  ans = min(ans, dp[n][i])

print(ans)



import sys

input = sys.stdin.readline



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

ab = [list(map(int, input().split())) for _ in range(N)]

mx = max([a for a,b in ab])

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

# i番目までの魔法を使った時にモンスターの体力をj減らすするのに必要な魔力の最少値

dp[0][0] = 0



for i in range(N):

  a, b = ab[i]

  for j in range(H+1+mx):

    if j - a >= 0:

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

    else:

      dp[i+1][j] = dp[i][j]



ans = float('inf')

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

  ans = min(ans, dp[N][i])

print(ans)

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = 0
for a, b in ab:
    max_a = max(max_a, a)
# i番目まで見たときに、モンスターの体力をj減らした時の、トキの消耗した魔力の最小値
dp = [[float("inf")] * (h + max_a + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(n):
    a, b = ab[i]
    for j in range(h + max_a + 1):
        if j - a >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b)
        else:
            dp[i + 1][j] = dp[i][j]
ans = float("inf")
for i in range(h, h + max_a + 1):
    ans = min(ans, dp[n][i])
print(ans)

import sys

input = sys.stdin.readline
H, N = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N)]
mx = max([a for a, b in ab])
dp = [[float("inf")] * (H + 1 + mx) for _ in range(N + 1)]
# i番目までの魔法を使った時にモンスターの体力をj減らすするのに必要な魔力の最少値
dp[0][0] = 0
for i in range(N):
    a, b = ab[i]
    for j in range(H + 1 + mx):
        if j - a >= 0:
            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
ans = float("inf")
for i in range(H, H + mx + 1):
    ans = min(ans, dp[N][i])
print(ans)

-h, n = list(map(int, input().split())) -ab = [list(map(int, input().split())) for _ in range(n)] -max_a = 0 -for a, b in ab: -    max_a = max(max_a, a) -# i番目まで見たときに、モンスターの体力をj減らした時の、トキの消耗した魔力の最小値 -dp = [[float("inf")] * (h + max_a + 1) for _ in range(n + 1)] -for i in range(n + 1): -    dp[i][0] = 0 -for i in range(n): +import sys + +input = sys.stdin.readline +H, N = list(map(int, input().split())) +ab = [list(map(int, input().split())) for _ in range(N)] +mx = max([a for a, b in ab]) +dp = [[float("inf")] * (H + 1 + mx) for _ in range(N + 1)] +# i番目までの魔法を使った時にモンスターの体力をj減らすするのに必要な魔力の最少値 +dp[0][0] = 0 +for i in range(N): -    for j in range(h + max_a + 1): +    for j in range(H + 1 + mx): -            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b) +            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j]) -for i in range(h, h + max_a + 1): -    ans = min(ans, dp[n][i]) +for i in range(H, H + mx + 1): +    ans = min(ans, dp[N][i])