CodeEff/ECCO huggingface dataset:
# Original solution
h,n=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(n)]
mx=max(a for a,b in ab)
dp=[10**10]*(h+1+mx)
dp[0]=0
for i in range(1,h+1+mx):
  dp[i]=min(dp[i-a]+b for a,b in ab)
print((min(dp[h:])))

# Optimized solution
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 8)
h,n=list(map(int,input().split()))
ab=[tuple(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda abi:(abi[1]/abi[0],abi[0]))

@lru_cache(maxsize=None)
def dp(i):
  if i<=0:
    return 0
  else:
    ans=float('inf')
    for a,b in ab:
      val=b+dp(i-a)
      if val<ans:
        ans=val
      else:
        break
    return ans

print((dp(h)))
# Original solution

H, N = (int(x) for x in input().split())

spells = []
for _ in range(N):
    a, b = (int(x) for x in input().split())

    spells.append((a,b))

spells.sort(reverse=True)

best = {}
best[0] = 0
cheapest = float('inf')
stack = [(0, 0)]
while len(stack):
    h, c = stack.pop()

    if h >= H:
        cheapest = min(c, cheapest)
        continue

    for a,b in spells:
        h2 = h + a
        c2 = c + b

        if h2 not in best or best[h2] > c2:
            stack.append((h2, c2))

            best[h2] = c2

print(cheapest)

# Optimized solution
from collections import deque

H, N = (int(x) for x in input().split())

spells = []
for _ in range(N):
    a, b = (int(x) for x in input().split())

    spells.append((a,b))

spells.sort(key=lambda spell: spell[1] / spell[0])

best = {}
cheapest = float('inf')
q = deque()
q.append((0,0))
while len(q):
    h, c = q.popleft()

    if h >= H:
        cheapest = min(c, cheapest)
        continue

    if h in best and best[h] < c:
        continue

    best[h] = c

    for a,b in spells:
        h2 = h + a
        c2 = c + b

        if h2 not in best or best[h2] > c2:
            q.append((h2, c2))
            best[h2] = c2

print(cheapest)
# Original solution
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
  A, B = list(map(int, input().split()))
  AB.append((A, B))

'''
H = 10000
N = 1000
import random
AB = []
for i in range(N):
    A = random.randint(1, 10000)
    B = random.randint(1, 10000)
    AB.append((A, B))
'''




@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    return min(b + f(h - a) for a, b in AB)

#AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]))
#bestA, bestB = AB[-1]

bestA, bestB = max(AB, key=lambda ab: (ab[0] / ab[1], -ab[0]))
threshold = sum(a for a, b in AB)

ans = None
times = (H - threshold) // bestA
if times > 0:
    ans = bestB * times + f(H - bestA * times)
else:
    ans = f(H)

print(ans)

# Optimized solution
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
  A, B = list(map(int, input().split()))
  AB.append((A, B))

'''
H = 10000
N = 1000
import random
AB = []
for i in range(N):
    A = random.randint(1, 10000)
    B = random.randint(1, 10000)
    AB.append((A, B))
'''




@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float('inf')
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        else:
            break
    return best

AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]
threshold = sum(a for a, b in AB)

ans = None
times = (H - threshold) // bestA
if times > 0:
    ans = bestB * times + f(H - bestA * times)
else:
    ans = f(H)

print(ans)
# Original solution
h, n = list(map(int, input().split()))

f_inf = float("inf")
dp = [f_inf] * (h + 1)
dp[0] = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(h):
        next_j = min(j + a, h)
        dp[next_j] = min(dp[next_j], dp[j] + b)

print((dp[h]))

# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    h, n = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(n)]

    dp = [f_inf] * (h + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(1, h + 1):
            dp[i] = min(dp[i], dp[max(0, i - a)] + b)

    print((dp[h]))


if __name__ == '__main__':
    resolve()
# Original solution
H,N = list(map(int,input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

dp = [0]*(H+1)

for i in range(1,H+1):
    dp[i] = min(dp[max(0,i-a)]+b for a,b in AB)
    
print((dp[H]))

# Optimized solution
H,N = list(map(int,input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

M = max(a for a,b in AB)

dp = [0]*(H+M)

for i in range(1,H+M):
    dp[i] = min(dp[i-a]+b for a,b in AB)
    
print((min(dp[H:])))
# Original solution
import sys
input = sys.stdin.readline

def I(): return int(eval(input()))
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,N=MI()
    A=[0]*N
    B=[0]*N
    
    for i in range(N):
        A[i],B[i]=MI()
        
    inf =10**20
    dp=[[inf]*(H+1)for _ in range(N+1)]
    # dp[i]はi番目の魔法まででhpをj減らす方法
    
    dp[0][0]=0
    
    for i in range(N):
        a=A[i]
        b=B[i]
        for j in range(H+1):
            dp[i+1][j]=min(dp[i+1][j],
                           dp[i][j])
            if j-a>=0:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i+1][j-a]+b)
            else:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i+1][0]+b)
                
    print((dp[-1][-1]))

main()


# Optimized solution
import sys
input = sys.stdin.readline

def I(): return int(eval(input()))
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,N=MI()
    A=[0]*N
    B=[0]*N
    
    for i in range(N):
        A[i],B[i]=MI()
        
    inf =10**20
    dp=[[inf]*(H+1)for _ in range(N+1)]
    # dp[i]はi番目の魔法まででhpをj減らす方法
    
    dp[0][0]=0
    
    for i in range(N):
        a=A[i]
        b=B[i]
        for j in range(H+1):
            if j-a>=0:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i][j],
                               dp[i+1][j-a]+b)
            else:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i][j],
                               dp[i+1][0]+b)
                
    print((dp[-1][-1]))

main()
# Original solution
H,N = list(map(int,input().split()))
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = list(map(int,input().split()))
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
#            KARI = []
            DP[i][j]=DP[i-1][j]
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
            r = j // Magic[i][0]
            for k in range(r):
                DP[i][j]=min(DP[i][j],(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1]))
print((min(DP[N-1][H:MAX_A])))

                
            
        


# Optimized solution
H,N = list(map(int,input().split()))
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = list(map(int,input().split()))
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print((min(DP[N-1][H:MAX_A])))
# Original solution
H,N = list(map(int,input().split()))
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = list(map(int,input().split()))
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print((min(DP[N-1][H:MAX_A])))

# Optimized solution
H,N = list(map(int,input().split()))
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = list(map(int,input().split()))
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
print((min(DP[N-1][H:MAX_A])))
# Original solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
      cost.pop(index[i])

print((min(anslist)))

# Optimized solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=ab[0][0]
    ans+=ab[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print((min(anslist)))
# Original solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=ab[0][0]
    ans+=ab[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print((min(anslist)))

# Optimized solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print((min(anslist)))
# Original solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print((min(anslist)))

# Optimized solution
h,n = list(map(int,input().split()))
ab = []
for i in range(n):
  a,b = list(map(int,input().split()))
  ab.append([a,b])

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print((139815))
  exit()


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print((min(anslist)))
# Original solution
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))

dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print((dp[-1]))


# Optimized solution
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print((dp[-1]))
# Original solution
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print((dp[-1]))

# Optimized solution
h, n = list(map(int, input().split()))
dp = [1000000000] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(h):
        # nj = min(j + a, h)
        if j + a < h: nj = j + a
        else: nj = h
        # dp[nj] = min(dp[nj], dp[j] + b)
        if dp[nj] > dp[j] + b: 
            dp[nj] = dp[j] + b
print((dp[h]))
# Original solution
h, ｎ = list(map(int, input().split()))
dp = [10**10] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  t = 10 ** 10
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    dp[ht] = min(dp[ht], dp[i] + j[1]) 

print((dp[h]))


# Optimized solution
h, ｎ = list(map(int, input().split()))
dp = [-1] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  if dp[i] == -1: continue
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    if dp[ht] != -1:
      dp[ht] = min(dp[ht], dp[i] + j[1])
    else:
      dp[ht] = dp[i] + j[1]

print((dp[h]))
# Original solution
from sys import stdin
input = stdin.readline


def main():
  H, N = list(map(int, input().split()))
  A = [0]*N
  B = [0]*N
  for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

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

  for i in range(1, N+1):
    for j in range(1, H+1):
      dp[i][j] = dp[i-1][j]
      if j > A[i-1]:
        dp[i][j] = min(dp[i][j], dp[i][j-A[i-1]]+B[i-1])
      else:
        dp[i][j] = min(dp[i][j], B[i-1])

  # for i in range(N+1):
  #   print(dp[i])
  print((dp[N][H]))


if(__name__ == '__main__'):
  main()

# Optimized solution
from sys import stdin
input = stdin.readline


def main():
  H, N = list(map(int, input().split()))
  A = [0]*N
  B = [0]*N
  for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

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

  for i in range(1, N+1):
    for j in range(1, H+1):
      # dp[i][j] = dp[i-1][j]
      if j > A[i-1]:
        dp[j] = min(dp[j], dp[j-A[i-1]]+B[i-1])
      else:
        dp[j] = min(dp[j], B[i-1])

  # for i in range(N+1):
  #   print(dp[i])
  print((dp[H]))


if(__name__ == '__main__'):
  main()
# Original solution
import copy

H,N=list(map(int,input().split()))
A=[]
B=[]
for _ in range(N):
    a,b=list(map(int,input().split()))
    A.append(copy.copy(a))
    B.append(copy.copy(b))


inf=float('inf')
component=[0]
for i in range(H):
    component.append(inf)
DP=[]
for j in range(N+1):
    DP.append(copy.copy(component))#DPは(N+1)×(H+1)


for k in range(1,N+1):#k番目の魔法
    for l in range(1,H+1):#体力H
        DP[k][l]=min(DP[k-1][l],DP[k][max(0,l-A[k-1])]+B[k-1])

print((DP[N][H]))










# Optimized solution
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)


inf=float('inf')
component=[0]
for i in range(H):
    component.append(inf)
DP=[]
for j in range(N+1):
    DP.append(component)#DPは(N+1)×(H+1)


for k in range(1,N+1):#k番目の魔法
    for l in range(1,H+1):#体力H
        DP[k][l]=min(DP[k-1][l],DP[k][max(0,l-A[k-1])]+B[k-1])

print((DP[N][H]))
# Original solution
import sys
h, n = list(map(int, input().split()))
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for ab in AB: # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print((dp[h]))


# Optimized solution
H, N = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print((dp[H]))
# Original solution
import sys
h, n = list(map(int, input().split()))
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = list(map(int, input().split()))
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
print((min(dp[h:])))


# Optimized solution
import sys
h, n = list(map(int, input().split()))
# A = [0] * n
# B = [0] * n
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print((min(dp[h:])))
# Original solution
h,n = list(map(int,input().split()))

ab_input = [[int(j) for j in input().split()] for i in range(n)]
#配るdp
dp =[10**10]*(h+1)
dp[0]=0
for i in range(h):
    for a,b in ab_input:
        next_index=min(h,i+a)
        dp[next_index]=min(dp[next_index],dp[i]+b)
print((dp[-1]))


    

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

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)
#配るdp
dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print((dp[h]))
# Original solution
h, n = list(map(int, input().split()))
INF = 10 ** 9
dp = [INF for _ in range(2*10**4)]
AB = [tuple(map(int, input().split())) for _ in range(n)]
dp[0] = 0
for a, b in AB:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print((min(dp[h:])))

# Optimized solution
def main():
    h, n = list(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF for _ in range(2*10**4)]
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    dp[0] = 0
    for a, b in AB:
        for i in range(h):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[h:])))
if __name__ == "__main__":
    main()