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

inf = 10**12

data = []

for i in range(n):

    data.append(list(map(int, input().split())))

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

for i in range(n):

    dp[i][0] = 0

for i in range(n):

    a, b = data[i]

    for j in range(h+1+10**4):

        if j - a >= 0:

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

        else:

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

print((dp[-1][h]))
h, n = list(map(int, input().split()))

inf = 10**10

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

#dp[i][j] := i番目の魔法まで考えたとき、hpをh減らす最小コスト

dp[0][0] = 0

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

    damage, cost = list(map(int, input().split()))

    for j in range(h+1):

        if j - damage < 0:

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

        else:

            dp[i][j] = min(dp[i][j - damage] + cost, dp[i-1][j])

print((dp[-1][h]))
h, n = list(map(int, input().split()))
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h + 1 + 10**4)] for j in range(n + 1)]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h + 1 + 10**4):
        if j - a >= 0:
            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        else:
            dp[i + 1][j] = min(b, dp[i][j])
print((dp[-1][h]))

h, n = list(map(int, input().split()))
inf = 10**10
dp = [[inf for i in range(h + 1)] for j in range(n + 1)]
# dp[i][j] := i番目の魔法まで考えたとき、hpをh減らす最小コスト
dp[0][0] = 0
for i in range(1, n + 1):
    damage, cost = list(map(int, input().split()))
    for j in range(h + 1):
        if j - damage < 0:
            dp[i][j] = min(cost, dp[i][j], dp[i - 1][j])
        else:
            dp[i][j] = min(dp[i][j - damage] + cost, dp[i - 1][j])
print((dp[-1][h]))

-inf = 10**12 -data = [] -for i in range(n): -    data.append(list(map(int, input().split()))) -dp = [[inf for i in range(h + 1 + 10**4)] for j in range(n + 1)] -for i in range(n): -    dp[i][0] = 0 -for i in range(n): -    a, b = data[i] -    for j in range(h + 1 + 10**4): -        if j - a >= 0: -            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j]) +inf = 10**10 +dp = [[inf for i in range(h + 1)] for j in range(n + 1)] +# dp[i][j] := i番目の魔法まで考えたとき、hpをh減らす最小コスト +dp[0][0] = 0 +for i in range(1, n + 1): +    damage, cost = list(map(int, input().split())) +    for j in range(h + 1): +        if j - damage < 0: +            dp[i][j] = min(cost, dp[i][j], dp[i - 1][j]) -            dp[i + 1][j] = min(b, dp[i][j]) +            dp[i][j] = min(dp[i][j - damage] + cost, dp[i - 1][j])