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

A = []

B = []

for _ in range(N):

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

    A.append(a)

    B.append(b)



# 個数制限なしナップサック

# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力

dp = [[float('inf')]*(H+1) for _ in range(N+1)]

dp[0][0] = 0

for i in range(N):

    for j in range(H+1):

        # i番目の魔法を使わない時

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

        # i番目の魔法を使う時

        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])



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

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

A = []

B = []

for _ in range(N):

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

    A.append(a)

    B.append(b)



# 個数制限なしナップサック

# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力

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

dp[0][0] = 0

for i in range(N):

    for j in range(H+1):

        # i番目の魔法を使わない時

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

        # i番目の魔法を使う時

        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])



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

H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[float("inf")] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        # i番目の魔法を使わない時
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i + 1][min(H, j + A[i])] = min(
            dp[i][j] + B[i], dp[i + 1][j] + B[i], dp[i + 1][min(j + A[i], H)]
        )
print((dp[N][H]))

H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[10**10] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        # i番目の魔法を使わない時
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i + 1][min(H, j + A[i])] = min(
            dp[i][j] + B[i], dp[i + 1][j] + B[i], dp[i + 1][min(j + A[i], H)]
        )
print((dp[N][H]))

-dp = [[float("inf")] * (H + 1) for _ in range(N + 1)] +dp = [[10**10] * (H + 1) for _ in range(N + 1)]