# AtCoder Beginner Contest 153

# E - Crested Ibis vs Monster

# https://atcoder.jp/contests/abc153/tasks/abc153_e

H, N, *A = list(map(int, open(0).read().split()))

*A, = list(zip(*[iter(A)]*2))



INF = 1 << 30

dp = [INF]*(H+1)

dp[0] = 0

for i, (a, b) in enumerate(A):

    for h in range(H+1):

        mh = min(H, h+a)

        dp[mh] = min(dp[mh], dp[h] + b)

print((dp[H]))

import sys

input = sys.stdin.buffer.readline

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

A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]

INF = 1 << 30

dp = [INF]*(H+1)

dp[H] = 0

for i in range(N):

    a, b = A[i]

    for h in range(H, -1, -1):

        x = h-a if h-a > 0 else 0

        if dp[x] > dp[h]+b:

            dp[x] = dp[h]+b

print((dp[0]))

# AtCoder Beginner Contest 153
# E - Crested Ibis vs Monster
# https://atcoder.jp/contests/abc153/tasks/abc153_e
H, N, *A = list(map(int, open(0).read().split()))
(*A,) = list(zip(*[iter(A)] * 2))
INF = 1 << 30
dp = [INF] * (H + 1)
dp[0] = 0
for i, (a, b) in enumerate(A):
    for h in range(H + 1):
        mh = min(H, h + a)
        dp[mh] = min(dp[mh], dp[h] + b)
print((dp[H]))

import sys

input = sys.stdin.buffer.readline
H, N = list(map(int, input().split()))
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
INF = 1 << 30
dp = [INF] * (H + 1)
dp[H] = 0
for i in range(N):
    a, b = A[i]
    for h in range(H, -1, -1):
        x = h - a if h - a > 0 else 0
        if dp[x] > dp[h] + b:
            dp[x] = dp[h] + b
print((dp[0]))

-# AtCoder Beginner Contest 153 -# E - Crested Ibis vs Monster -# https://atcoder.jp/contests/abc153/tasks/abc153_e -H, N, *A = list(map(int, open(0).read().split())) -(*A,) = list(zip(*[iter(A)] * 2)) +import sys + +input = sys.stdin.buffer.readline +H, N = list(map(int, input().split())) +A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()] -dp[0] = 0 -for i, (a, b) in enumerate(A): -    for h in range(H + 1): -        mh = min(H, h + a) -        dp[mh] = min(dp[mh], dp[h] + b) -print((dp[H])) +dp[H] = 0 +for i in range(N): +    a, b = A[i] +    for h in range(H, -1, -1): +        x = h - a if h - a > 0 else 0 +        if dp[x] > dp[h] + b: +            dp[x] = dp[h] + b +print((dp[0]))