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

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



dp = [10**18] * (h + 1 + 10 ** 5)

dp[h + 10 ** 5] = 0

for i in range(n):

    a, b = info[i]

    for j in range(h + 1 + 10 ** 5)[::-1]:

        if j - a >= 0:

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

print((min(dp[0:10**5 + 1])))

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

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

INF = 10**18



dp = [INF] * (h + 1)

dp[h] = 0

for i in range(n):

    a, b = info[i]

    for j in range(h + 1)[::-1]:

            dp[max(j - a, 0)] = min(dp[j] + b, dp[max(j - a, 0)])

print((dp[0]))

h, n = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n)]
dp = [10**18] * (h + 1 + 10**5)
dp[h + 10**5] = 0
for i in range(n):
    a, b = info[i]
    for j in range(h + 1 + 10**5)[::-1]:
        if j - a >= 0:
            dp[j - a] = min(dp[j] + b, dp[j - a])
print((min(dp[0 : 10**5 + 1])))

h, n = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n)]
INF = 10**18
dp = [INF] * (h + 1)
dp[h] = 0
for i in range(n):
    a, b = info[i]
    for j in range(h + 1)[::-1]:
        dp[max(j - a, 0)] = min(dp[j] + b, dp[max(j - a, 0)])
print((dp[0]))

-dp = [10**18] * (h + 1 + 10**5) -dp[h + 10**5] = 0 +INF = 10**18 +dp = [INF] * (h + 1) +dp[h] = 0 -    for j in range(h + 1 + 10**5)[::-1]: -        if j - a >= 0: -            dp[j - a] = min(dp[j] + b, dp[j - a]) -print((min(dp[0 : 10**5 + 1]))) +    for j in range(h + 1)[::-1]: +        dp[max(j - a, 0)] = min(dp[j] + b, dp[max(j - a, 0)]) +print((dp[0]))