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

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

maxa=max([a for a,b in ab])

maxmp=pow(10,8)

dp=[maxmp]*(h+maxa) # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力

dp[0]=0

for i in range(h+maxa):

  b=[dp[i-a]+b for a,b in ab if i-a>=0]

  dp[i]=min(dp[i],min(b)) if b else dp[i]

print((min(dp[h:])))

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

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

inf=float('inf')

dp=[inf]*(h+1)

# dp[i]:ダメージiを与えるための最小魔力

dp[0]=0

for a,b in ab:

  # a:ダメージ,b:魔力

  ndp=[inf]*(h+1)

  ndp[0]=0

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

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

  dp=ndp

print((dp[h]))
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
maxa = max([a for a, b in ab])
maxmp = pow(10, 8)
dp = [maxmp] * (h + maxa)  # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力
dp[0] = 0
for i in range(h + maxa):
    b = [dp[i - a] + b for a, b in ab if i - a >= 0]
    dp[i] = min(dp[i], min(b)) if b else dp[i]
print((min(dp[h:])))

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
inf = float("inf")
dp = [inf] * (h + 1)
# dp[i]:ダメージiを与えるための最小魔力
dp[0] = 0
for a, b in ab:
    # a:ダメージ,b:魔力
    ndp = [inf] * (h + 1)
    ndp[0] = 0
    for i in range(1, h + 1):
        ndp[i] = min(dp[i], ndp[max(0, i - a)] + b)
    dp = ndp
print((dp[h]))

-maxa = max([a for a, b in ab]) -maxmp = pow(10, 8) -dp = [maxmp] * (h + maxa)  # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力 +inf = float("inf") +dp = [inf] * (h + 1) +# dp[i]:ダメージiを与えるための最小魔力 -for i in range(h + maxa): -    b = [dp[i - a] + b for a, b in ab if i - a >= 0] -    dp[i] = min(dp[i], min(b)) if b else dp[i] -print((min(dp[h:]))) +for a, b in ab: +    # a:ダメージ,b:魔力 +    ndp = [inf] * (h + 1) +    ndp[0] = 0 +    for i in range(1, h + 1): +        ndp[i] = min(dp[i], ndp[max(0, i - a)] + b) +    dp = ndp +print((dp[h]))