#モンスターの体力は H

#トキはN種類の魔法が使え、

#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、

#トキの魔力を Bi消耗します。



#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値

#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])

#dp[0]=0



import numpy as np

 

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

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

ab = np.array(ab)

 

a = ab[:, 0]

b = ab[:, 1]

 

dp = np.zeros(100001, dtype=np.int)

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

    dp[i] = (dp[i-a]+b).min()

print((dp[h]))

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

a = []

b = []

for i in range(n):

    a_, b_ = list(map(int, input().split()))

    a.append(a_)

    b.append(b_)



dp = [10**9] * (h+1)

dp[0] = 0



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

    for j in range(n):

        dp[i] = min(dp[i], dp[max(i-a[j], 0)] + b[j])



print((dp[-1]))

# モンスターの体力は H
# トキはN種類の魔法が使え、
# i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
# トキの魔力を Bi消耗します。
# dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
# dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
# dp[0]=0
import numpy as np

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab)
a = ab[:, 0]
b = ab[:, 1]
dp = np.zeros(100001, dtype=np.int)
for i in range(1, h + 1):
    dp[i] = (dp[i - a] + b).min()
print((dp[h]))

h, n = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a_, b_ = list(map(int, input().split()))
    a.append(a_)
    b.append(b_)
dp = [10**9] * (h + 1)
dp[0] = 0
for i in range(1, h + 1):
    for j in range(n):
        dp[i] = min(dp[i], dp[max(i - a[j], 0)] + b[j])
print((dp[-1]))

-# モンスターの体力は H -# トキはN種類の魔法が使え、 -# i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、 -# トキの魔力を Bi消耗します。 -# dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値 -# dp[i+1] = min(dp[i-Ai]+Bi,dp[i]) -# dp[0]=0 -import numpy as np - -ab = [list(map(int, input().split())) for _ in range(n)] -ab = np.array(ab) -a = ab[:, 0] -b = ab[:, 1] -dp = np.zeros(100001, dtype=np.int) +a = [] +b = [] +for i in range(n): +    a_, b_ = list(map(int, input().split())) +    a.append(a_) +    b.append(b_) +dp = [10**9] * (h + 1) +dp[0] = 0 -    dp[i] = (dp[i - a] + b).min() -print((dp[h])) +    for j in range(n): +        dp[i] = min(dp[i], dp[max(i - a[j], 0)] + b[j]) +print((dp[-1]))