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

magic = []

INF = 10**8

dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値

 

for i in range(n):

    a,b = list(map(int, input().split()))

    magic.append([a, b])

 

for i in range(n):

    for j in range(h):

        if j+1 > magic[i][0]:

            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])

        else:

            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])

            

print((dp[n][h]))
inf = 10**15

mod = 10**9+7

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

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

dp = [[inf for j in range(h+1)] for i in range(n+1)]

for i in range(n):

    dp[i][0] = 0

    a,b = ab[i]

    for j in range(h):

        if j+1-a>=0:

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

        else:

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

print((dp[n][h]))
h, n = list(map(int, input().split()))
magic = []
INF = 10**8
dp = [
    [INF for j in range(h + 1)] for i in range(n + 1)
]  # 体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値
for i in range(n):
    a, b = list(map(int, input().split()))
    magic.append([a, b])
for i in range(n):
    for j in range(h):
        if j + 1 > magic[i][0]:
            dp[i + 1][j + 1] = min(
                dp[i][j + 1],
                dp[i][j + 1 - magic[i][0]] + magic[i][1],
                dp[i + 1][j + 1 - magic[i][0]] + magic[i][1],
            )
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1], magic[i][1])
print((dp[n][h]))

inf = 10**15
mod = 10**9 + 7
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]
dp = [[inf for j in range(h + 1)] for i in range(n + 1)]
for i in range(n):
    dp[i][0] = 0
    a, b = ab[i]
    for j in range(h):
        if j + 1 - a >= 0:
            dp[i + 1][j + 1] = min(
                dp[i + 1][j + 1 - a] + b, dp[i][j + 1], dp[i][j + 1 - a] + b
            )
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1], b)
print((dp[n][h]))

+inf = 10**15 +mod = 10**9 + 7 -magic = [] -INF = 10**8 -dp = [ -    [INF for j in range(h + 1)] for i in range(n + 1) -]  # 体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値 +ab = [list(map(int, input().split())) for i in range(n)] +dp = [[inf for j in range(h + 1)] for i in range(n + 1)] -    a, b = list(map(int, input().split())) -    magic.append([a, b]) -for i in range(n): +    dp[i][0] = 0 +    a, b = ab[i] -        if j + 1 > magic[i][0]: +        if j + 1 - a >= 0: -                dp[i][j + 1], -                dp[i][j + 1 - magic[i][0]] + magic[i][1], -                dp[i + 1][j + 1 - magic[i][0]] + magic[i][1], +                dp[i + 1][j + 1 - a] + b, dp[i][j + 1], dp[i][j + 1 - a] + b -            dp[i + 1][j + 1] = min(dp[i][j + 1], magic[i][1]) +            dp[i + 1][j + 1] = min(dp[i][j + 1], b)