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

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

A.insert(0,[0,0])

INFTY = 10**9

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

for i in range(N+1):

    dp[i][0] = 0

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

    for j in range(1,H+1):

        dp[i][j] = dp[i-1][j]

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

print((dp[N][H]))
H,N = list(map(int,input().split()))

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

INFTY = 10**8

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

for i in range(N+1):

    dp[i][0] = 0

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

    for j in range(1,H+1):

        dp[i][j] = dp[i-1][j]

        if j>=A[i-1][0]:

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

        else:

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

print((dp[N][H]))
H, N = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
A.insert(0, [0, 0])
INFTY = 10**9
dp = [[INFTY for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    for j in range(1, H + 1):
        dp[i][j] = dp[i - 1][j]
        dp[i][j] = min(dp[i][j], dp[i][max(0, j - A[i][0])] + A[i][1])
print((dp[N][H]))

H, N = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
INFTY = 10**8
dp = [[INFTY for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    for j in range(1, H + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= A[i - 1][0]:
            dp[i][j] = min(dp[i][j], dp[i][j - A[i - 1][0]] + A[i - 1][1])
        else:
            dp[i][j] = min(dp[i][j], A[i - 1][1])
print((dp[N][H]))

-A.insert(0, [0, 0]) -INFTY = 10**9 +INFTY = 10**8 -        dp[i][j] = min(dp[i][j], dp[i][max(0, j - A[i][0])] + A[i][1]) +        if j >= A[i - 1][0]: +            dp[i][j] = min(dp[i][j], dp[i][j - A[i - 1][0]] + A[i - 1][1]) +        else: +            dp[i][j] = min(dp[i][j], A[i - 1][1])