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

INF = 10 ** 12



M = []

for i in range(N):

    A, B = list(map(int, input().split()))

    M.append((A, B))





dp = [[INF for j in range(H+10**4+1)] for i in range(N+1)]





# for i in range(N+1):

#     dp[0][i] = 0



for i in range(N+1):

    dp[i][0] = 0



for i in range(1, N+1):  # 1<= i <= N

    # for j in range(1, H+10**4+1):  # 1 <= j <= H

    for j in range(1, H+1):  # 1 <= j <= H

        # print(i, j)

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

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

                           dp[i][j - M[i-1][0]] + M[i-1][1])

        else:

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





# for i in range(N+1):

#     print(dp[i][H])



# ans = INF

# for i in range(H, H+10**4+1):

#     ans = min(ans, dp[N][i])

# print(ans)



print((dp[N][H]))

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

INF = 10 ** 12



M = []

for i in range(N):

    A, B = list(map(int, input().split()))

    M.append((A, B))



dp = [INF for j in range(H+10**4+1)]

dp[0] = 0



for i in range(N):

    for j in range(1, H+10**4+1):

        if j - M[i][0] >= 0:

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



ans = INF

for i in range(10**4+1):

    ans = min(ans, dp[H+i])

print(ans)

H, N = list(map(int, input().split()))
INF = 10**12
M = []
for i in range(N):
    A, B = list(map(int, input().split()))
    M.append((A, B))
dp = [[INF for j in range(H + 10**4 + 1)] for i in range(N + 1)]
# for i in range(N+1):
#     dp[0][i] = 0
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):  # 1<= i <= N
    # for j in range(1, H+10**4+1):  # 1 <= j <= H
    for j in range(1, H + 1):  # 1 <= j <= H
        # print(i, j)
        if j - M[i - 1][0] >= 0:
            dp[i][j] = min(
                dp[i - 1][j],
                dp[i - 1][j - M[i - 1][0]] + M[i - 1][1],
                dp[i][j - M[i - 1][0]] + M[i - 1][1],
            )
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][0] + M[i - 1][1])
# for i in range(N+1):
#     print(dp[i][H])
# ans = INF
# for i in range(H, H+10**4+1):
#     ans = min(ans, dp[N][i])
# print(ans)
print((dp[N][H]))

H, N = list(map(int, input().split()))
INF = 10**12
M = []
for i in range(N):
    A, B = list(map(int, input().split()))
    M.append((A, B))
dp = [INF for j in range(H + 10**4 + 1)]
dp[0] = 0
for i in range(N):
    for j in range(1, H + 10**4 + 1):
        if j - M[i][0] >= 0:
            dp[j] = min(dp[j], dp[j - M[i][0]] + M[i][1])
ans = INF
for i in range(10**4 + 1):
    ans = min(ans, dp[H + i])
print(ans)

-dp = [[INF for j in range(H + 10**4 + 1)] for i in range(N + 1)] -# for i in range(N+1): -#     dp[0][i] = 0 -for i in range(N + 1): -    dp[i][0] = 0 -for i in range(1, N + 1):  # 1<= i <= N -    # for j in range(1, H+10**4+1):  # 1 <= j <= H -    for j in range(1, H + 1):  # 1 <= j <= H -        # print(i, j) -        if j - M[i - 1][0] >= 0: -            dp[i][j] = min( -                dp[i - 1][j], -                dp[i - 1][j - M[i - 1][0]] + M[i - 1][1], -                dp[i][j - M[i - 1][0]] + M[i - 1][1], -            ) -        else: -            dp[i][j] = min(dp[i - 1][j], dp[i][0] + M[i - 1][1]) -# for i in range(N+1): -#     print(dp[i][H]) -# ans = INF -# for i in range(H, H+10**4+1): -#     ans = min(ans, dp[N][i]) -# print(ans) -print((dp[N][H])) +dp = [INF for j in range(H + 10**4 + 1)] +dp[0] = 0 +for i in range(N): +    for j in range(1, H + 10**4 + 1): +        if j - M[i][0] >= 0: +            dp[j] = min(dp[j], dp[j - M[i][0]] + M[i][1]) +ans = INF +for i in range(10**4 + 1): +    ans = min(ans, dp[H + i]) +print(ans)