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

ab = []

for _ in range(n):

    a, b = (int(x) for x in input().split())

    ab.append([a, b])



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



for i in range(n):

    for j in range(h+1):

        if j <= ab[i][0]:

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

        else:

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



print((dp[-1][-1]))

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



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



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



for y in range(N):

    a,b = AB[y]

    for x in range(H+1):

        if x <= a:

            dp[y+1][x] = min(dp[y][x], b)

        else:

            dp[y+1][x] = min(dp[y][x], dp[y+1][x-a]+b)

print((dp[-1][-1]))
h, n = list(map(int, input().split()))
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [[100000000 for i in range(h + 1)] for j in range(n + 1)]
for i in range(n):
    for j in range(h + 1):
        if j <= ab[i][0]:
            dp[i + 1][j] = min(ab[i][1], dp[i][j])
        else:
            dp[i + 1][j] = min(ab[i][1] + dp[i + 1][j - ab[i][0]], dp[i][j])
print((dp[-1][-1]))

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[10000000000000] * (H + 1) for _ in range(N + 1)]
for y in range(N):
    a, b = AB[y]
    for x in range(H + 1):
        if x <= a:
            dp[y + 1][x] = min(dp[y][x], b)
        else:
            dp[y + 1][x] = min(dp[y][x], dp[y + 1][x - a] + b)
print((dp[-1][-1]))

-h, n = list(map(int, input().split())) -ab = [] -for _ in range(n): -    a, b = (int(x) for x in input().split()) -    ab.append([a, b]) -dp = [[100000000 for i in range(h + 1)] for j in range(n + 1)] -for i in range(n): -    for j in range(h + 1): -        if j <= ab[i][0]: -            dp[i + 1][j] = min(ab[i][1], dp[i][j]) +H, N = list(map(int, input().split())) +AB = [list(map(int, input().split())) for _ in range(N)] +dp = [[10000000000000] * (H + 1) for _ in range(N + 1)] +for y in range(N): +    a, b = AB[y] +    for x in range(H + 1): +        if x <= a: +            dp[y + 1][x] = min(dp[y][x], b) -            dp[i + 1][j] = min(ab[i][1] + dp[i + 1][j - ab[i][0]], dp[i][j]) +            dp[y + 1][x] = min(dp[y][x], dp[y + 1][x - a] + b)