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

ab = []

for i in range(n):

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

###一次元DP

dp = [100000000] * (h+1)

dp[0] = 0

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

    for j in range(n):

        a = ab[j][0]

        b = ab[j][1]

        # print(i, j)

        temp = i - a

        if temp < 0:

            temp = 0

        need_magic = dp[temp] + b

        if need_magic < dp[i]:

            dp[i] = need_magic

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

        # print(i, j, a, b, dp)

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

dp = [1000000000] * (h+1)

dp[0] = 0

for i in range(n):

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

    for j in range(h):

        # nj = min(j + a, h)

        if j + a < h: nj = j + a

        else: nj = h

        # dp[nj] = min(dp[nj], dp[j] + b)

        if dp[nj] > dp[j] + b: 

            dp[nj] = dp[j] + b

print((dp[h]))
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h + 1)
dp[0] = 0
for i in range(1, h + 1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print((dp[-1]))

h, n = list(map(int, input().split()))
dp = [1000000000] * (h + 1)
dp[0] = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(h):
        # nj = min(j + a, h)
        if j + a < h:
            nj = j + a
        else:
            nj = h
        # dp[nj] = min(dp[nj], dp[j] + b)
        if dp[nj] > dp[j] + b:
            dp[nj] = dp[j] + b
print((dp[h]))

-ab = [] +dp = [1000000000] * (h + 1) +dp[0] = 0 -    ab.append(list(map(int, input().split()))) -###一次元DP -dp = [100000000] * (h + 1) -dp[0] = 0 -for i in range(1, h + 1): -    for j in range(n): -        a = ab[j][0] -        b = ab[j][1] -        # print(i, j) -        temp = i - a -        if temp < 0: -            temp = 0 -        need_magic = dp[temp] + b -        if need_magic < dp[i]: -            dp[i] = need_magic -        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b) -        # print(i, j, a, b, dp) -print((dp[-1])) +    a, b = list(map(int, input().split())) +    for j in range(h): +        # nj = min(j + a, h) +        if j + a < h: +            nj = j + a +        else: +            nj = h +        # dp[nj] = min(dp[nj], dp[j] + b) +        if dp[nj] > dp[j] + b: +            dp[nj] = dp[j] + b +print((dp[h]))