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

A = []

for i in range(N):

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

    A.append(a)



INF = float('INF')

MAX_J = (10 ** 4 + 1) * 2



# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値

DP = [INF] * MAX_J

DP[0] = 0



for i in range(N):

    for j in range(MAX_J):

        nj = min(j+A[i][0], H)

        DP[nj] = min(DP[nj], DP[j] + A[i][1])



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

A = []

for i in range(N):

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

    A.append(a)



INF = float('INF')

# MAX_J = (10 ** 4 + 1) * 2

MAX_J = 10 ** 4 + 1



# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値

DP = [INF] * MAX_J

DP[0] = 0



for i in range(N):

    for j in range(MAX_J):

        # nj: 求める添字

        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）

        nj = min(j+A[i][0], H)

        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か

        DP[nj] = min(DP[nj], DP[j] + A[i][1])

    # print(i, DP)



print((DP[H]))
H, N = list(map(int, input().split()))
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
INF = float("INF")
MAX_J = (10**4 + 1) * 2
# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0
for i in range(N):
    for j in range(MAX_J):
        nj = min(j + A[i][0], H)
        DP[nj] = min(DP[nj], DP[j] + A[i][1])
print((DP[H]))

H, N = list(map(int, input().split()))
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
INF = float("INF")
# MAX_J = (10 ** 4 + 1) * 2
MAX_J = 10**4 + 1
# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0
for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j + A[i][0], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + A[i][1])
    # print(i, DP)
print((DP[H]))

-MAX_J = (10**4 + 1) * 2 +# MAX_J = (10 ** 4 + 1) * 2 +MAX_J = 10**4 + 1 +        # nj: 求める添字 +        # nj: i番目の魔法を使った後のダメージの総和（Hがmax） +        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か +    # print(i, DP)