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

AB = [list(map(int,input().split())) for _ in range(N)]

dp = [[10**18]*(N+1) for _ in range(H+1)]

dp[0][0] = 0

for h in range(H+1):

    for i in range(N):

        dp[h][i+1] = min(dp[h][i], dp[max(0,h-AB[i][0])][i+1] + AB[i][1])

print((dp[H][N]))
inf = 10**9

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

AB = []

for n in range(N):

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

    AB.append((a, b))

AB.sort(reverse=True, key=lambda x: x[0])

dp = [inf] * (H + 10 ** 4)

dp[0] = 0

for a, b in AB:

    for h in range(H):

        if dp[h] != inf:

            tmp = dp[h] + b

            if tmp < dp[h + a]:

                dp[h + a] = tmp

print((min(dp[H:])))

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[10**18] * (N + 1) for _ in range(H + 1)]
dp[0][0] = 0
for h in range(H + 1):
    for i in range(N):
        dp[h][i + 1] = min(dp[h][i], dp[max(0, h - AB[i][0])][i + 1] + AB[i][1])
print((dp[H][N]))

inf = 10**9
H, N = list(map(int, input().split()))
AB = []
for n in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10**4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print((min(dp[H:])))

+inf = 10**9 -AB = [list(map(int, input().split())) for _ in range(N)] -dp = [[10**18] * (N + 1) for _ in range(H + 1)] -dp[0][0] = 0 -for h in range(H + 1): -    for i in range(N): -        dp[h][i + 1] = min(dp[h][i], dp[max(0, h - AB[i][0])][i + 1] + AB[i][1]) -print((dp[H][N])) +AB = [] +for n in range(N): +    a, b = list(map(int, input().split())) +    AB.append((a, b)) +AB.sort(reverse=True, key=lambda x: x[0]) +dp = [inf] * (H + 10**4) +dp[0] = 0 +for a, b in AB: +    for h in range(H): +        if dp[h] != inf: +            tmp = dp[h] + b +            if tmp < dp[h + a]: +                dp[h + a] = tmp +print((min(dp[H:])))