Problem:
 Score : 500 points    Problem Statement Ibis is fighting with a monster.  The health of the monster is H .  Ibis can cast N kinds of spells. Casting the i -th spell decreases the monster's health by A_i , at the cost of B_i Magic Points.  The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.  Ibis wins when the health of the monster becomes 0 or below.  Find the minimum total Magic Points that have to be consumed before winning.      Constraints  1 \leq H \leq 10^4  1 \leq N \leq 10^3  1 \leq A_i \leq 10^4  1 \leq B_i \leq 10^4  All values in input are integers.         Input Input is given from Standard Input in the following format:  H  N  A_1  B_1  :  A_N  B_N       Output Print the minimum total Magic Points that have to be consumed before winning.        Sample Input 1 9 3
8 3
4 2
2 1      Sample Output 1 4  First, let us cast the first spell to decrease the monster's health by 8 , at the cost of 3 Magic Points. The monster's health is now 1 .  Then, cast the third spell to decrease the monster's health by 2 , at the cost of 1 Magic Point. The monster's health is now -1 .  In this way, we can win at the total cost of 4 Magic Points.       Sample Input 2 100 6
1 1
2 3
3 9
4 27
5 81
6 243      Sample Output 2 100  It is optimal to cast the first spell 100 times.       Sample Input 3 9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461      Sample Output 3 139815

Solution (Python):
import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])

dp = np.zeros(h + 1, dtype="int")

for i in range(1, h+1):
    dpi_1 = dp[np.maximum(i - ab[:, 0], 0)]
    dpi = dpi_1 + ab[:, 1]
    dp[i] = np.min(dpi)
    
print(dp[-1])

Solution (Python):
h, n = map(int, input().split())
spells = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 9
dp = [INF] * (h + 1)
dp[0] = 0

for i in range(h):
    for a, b in spells:
        ni = min(i + a, h)
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[h])

Solution (Python):


import math

H, N = map(int, input().split())
AB = []
for i in range(N):
    a_tmp, b_tmp = map(int, input().split())
    AB.append([a_tmp, b_tmp])

dp=[0]*(H+max(s for s,t in AB))

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

print(dp[H])

Solution (Python):
h,n=map(int,input().split())
AB=[]
A=[]
for i in range(n):
    a,b=map(int,input().split())
    AB.append((a,b))
    A.append(a)
maA=max(A)

dp=[float("inf")]*(h+maA+1)
dp[0]=0

for i in range(h):
    for a,b in AB:
        dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

Solution (Python):
H,N = map(int,input().split())
p = []
for i in range(N):
    t = list( map( int, input().split() ) )
    p.append(t)

a = max(p)[0]
dp = [10**9] * (H+1+a)
dp[0] = 0

for i in range(H+1+a):
    for j in range(N):
        if i-p[j][0] >= 0:
            dp[i] = min(dp[i],dp[i-p[j][0]]+p[j][1])

print(min(dp[H:H+a]))

Solution (Python):
h, n = map(int, input().split()) 
magics = sorted([list(map(int, input().split())) for _ in range(n)])
max_a = magics[-1][0]

dp = [float("inf")] * (h + max_a)
dp[0] = 0

for ai, bi in magics:
  for i in range(h + max_a - ai):
    if dp[i] != float("inf"):
      dp[i + ai] = min(dp[i] + bi, dp[i + ai])


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

Solution (Python):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0

for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))

Solution (Python):

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)

dp=[[float("inf")]*(h+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    for j in range(h+1):
        
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        
        dp[i+1][min(j+a[i],h)]=min(dp[i+1][min(j+a[i],h)],dp[i+1][j]+b[i])    
        
print(dp[n][h])

Solution (Python):
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [0] * (w + max(a for a, b in ab))

for j in range(1, w+1):
    dp[j] = min(dp[j-a]+b for a, b in ab)

print(dp[w])

Solution (Python):
h,n=map(int,input().split())
A=[]
AB=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    AB.append((a,b))

maA=max(A)
dp=[float("inf")]*(h+maA+1)
dp[0]=0
for i in range(h+1):
    for a,b in AB:
        dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

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

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

if __name__ == '__main__':
    main()

Solution (Python):
H, N = map(int, input().split())
l = []
for i in range(N):
    a, b = map(int, input().split())
    l.append((a, b))
inf = 1e10
dp = [inf] * (H+1)
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        (a, b) = l[j]
        if i >= a:
            dp[i] = min(dp[i], dp[i-a]+b)
        else:
            dp[i] = min(dp[i], b)
print(dp[H])

Solution (Python):
H, N = map(int, input().split())
ATK = []

for i in range(N):	
  ATK.append(list(map(int, input().split())))
mp_min = [0]
for hp in range(1, H+1):
  mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

 

print(mp_min[-1])

Solution (Python):
def solve():
    N, M = map(int, input().split())
    A = []
    B = []
    dp = [float('inf')] * (N + 20000)
    dp[0] = 0
    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 10000):
            if dp[i] == 'inf':
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
        
    return min(dp[N:])

print(solve())

Solution (Python):
H,N=map(int,input().split())
a=[]
max_x=-10**10
for i in range(N):
  x,y=map(int,input().split())
  if x>max_x:
    max_x=x
  a.append([x,y])
  
dp = [0] * (H+max_x)
for i in range(0,H+max_x):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-l[0]]+l[1] for l in a )
print(dp[H])

Solution (Python):
from sys import stdin, stdout	

def sol2():
	H, N = (int(x) for x in stdin.readline().split())
	dp = [float('inf') for _ in range(H+1)]
	dp[0] = 0
	for line in stdin:
		dmg, cost = [int(x) for x in line.split()]
		for i in range(len(dp)):
			new = min(H, i + dmg)
			dp[new] = min(dp[new], dp[i] + cost)
	stdout.write(str(dp[-1]))

if __name__ == "__main__":
	sol2()

Solution (Python):
import sys
from io import StringIO
import unittest

def resolve():

    hp_max = (10**4)*3

    dp=[-1]*hp_max
    dp[0]=0

    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()))

    for hp in range((10**4)*2):
        if dp[hp]==-1:
            continue
        for i in range(n):
            nhp = hp+a[i]
            cost = dp[hp]+b[i]
            if dp[nhp]==-1:
                dp[nhp]=cost
            elif cost <= dp[nhp]:
                dp[nhp]=cost

    min_cost=0

    for hp in range(h,hp_max):
        if dp[hp]==-1:
            continue

        cost = dp[hp]

        if min_cost == 0:
            min_cost = cost
        elif cost<min_cost:
            min_cost = cost
    
    print(min_cost)

    return

resolve()

Solution (Python):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

dp = [2e9] * (H+1)
dp[0] = 0

for i in range(N):
  for h in range(H+AB[i][0]):
    if h - AB[i][0] < 0:
      continue
    else:
      dp[min(h, H)] = min(dp[min(h, H)], dp[h-AB[i][0]] + AB[i][1])

print(dp[H])

Solution (Python):

h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)

INF=float("inf")
    
dp=([[INF]*(1+h) for i in range(1+n)])


dp[0][0]=0

for i in range(n):
    
    for j in range(h+1):
        
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][min(h,j+a[i])]=min(dp[i+1][min(h,j+a[i])],dp[i+1][j]+b[i])
        
    


print(dp[n][h])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
ab=[]
for i in range(n):
    x,y=LI()
    ab.append((x,y))
ab.sort(key=lambda x:-x[0])
a=[i for i,j in ab]
b=[j for i,j in ab]
dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

for i in range(n):
    for j in range(h+1):
        dp[i+1][min(h,j+a[i])]=min(dp[i+1][j]+b[i],dp[i+1][min(h,j+a[i])],dp[i][min(h,j+a[i])])

ans=dp[n][h]

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
ab=[]
for i in range(n):
    x,y=LI()
    ab.append((-x,y))
ab.sort()
a=[-i for i,j in ab]
b=[j for i,j in ab]
dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

for i in range(n):
    for j in range(h+1):
        dp[i+1][min(h,j+a[i])]=min(dp[i+1][j]+b[i],dp[i+1][min(h,j+a[i])],dp[i][min(h,j+a[i])])

ans=dp[n][h]

print(ans)

Solution (Python):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Solution (Python):
h, n = list(map(int,input().split()))
a = [list(map(int,input().split())) for _ in range(n)]

INF = 10**18
dp = [INF]*(h+10001)

dp[0] = 0

for i in range(n):
  for j in range(h):
    if dp[j] == INF:
      continue
    dp[j+a[i][0]] = min(dp[j+a[i][0]],dp[j]+a[i][1])
print(min(dp[h:]))

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[0]+[inf]*h

for i in range(n):
    for j in range(h+1):
        dp[min(h,j+a[i])]=min(dp[j]+b[i],dp[min(h,j+a[i])])

ans=dp[h]

print(ans)

Solution (Python):
H, N = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))
max_a = max(ab[0] for ab in AB)
table = [0] + [float('inf')] * (H + max_a)

for i in range(N):
    for j in range(AB[i][0], H + max_a):
        table[j] = min(table[j], table[j - AB[i][0]] + AB[i][1])
print(min(table[H:]))

Solution (Python):








mod = int(1e9+7)

def main():
    h,n = map(int,input().split())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        a[i],b[i] = map(int,input().split())
    dp = [int(1e9)] * (h + max(a) + 10)
    dp[0] = 0
    for i in range(n):
        for j in range(1,h+max(a)):
            if a[i] <= j:
                dp[j] = min(dp[j - a[i]] + b[i],dp[j])
    ans = int(1e9)
    for i in range(h,h+max(a)):
        ans = min(ans,dp[i])
    print(ans)
    return

if __name__=='__main__':
    main()

Solution (Python):
H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [10000000000] * 10001
dp[0] = 0
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp[next] = min(dp[next], dp[j] + B[i])
print(dp[H])

Solution (Python):
h,n = map(int,input().split())
dp = [int(1e18)] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)
print(dp[h])

Solution (Python):
from heapq import heappush,heappop
import queue
import re
import math
import functools


def i_raw():
    return int(input())

def ss_raw():
    return input().split()

def is_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


def main():
    H,N = is_raw()
    ABs = [is_raw() for _ in range(N)]
    MA = max([ab[0] for ab in ABs])
    dp = [INF]*(H+MA+1)
    dp[0]=0
    for h in range(1,len(dp)):
        for ab in ABs:
            a,b = ab
            if h < a:
                continue
            dp[h] = min(dp[h],b+dp[h-a])
    return min([dp[h] for h in range(H,len(dp))])


print(main())

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    H, N = map(int, f_i.readline().split())
    
    dp = [10 ** 8] * (H + 10 ** 4)
    dp[0] = 0
    
    for i in range(N):
        A, B = map(int, f_i.readline().split())
        for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
            dp_i, dp_j = t
            if dp_i + B < dp_j:
                dp[j] = dp_i + B
    
    print(min(dp[H:]))

solve()

Solution (Python):
h, n = map(int, input().split())
magic = [0]*(h+1)
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        if (magic[j] or j == 0):
            if j == h:
                continue
            key = min([j+a, h])
            if magic[key] == 0:
                magic[key] = magic[j] + b
            else:
                magic[key] = min([magic[key], magic[j]+b])
print(magic[h])

Solution (Python):
H,N = list(map(int, input().split()))
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 

dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])

Solution (Python):
h, n = map(int, input().split())
dat = [list(map(int, input().split())) for _ in range(n)]
dp = [[10**9 for _ in range(h+1)] for _ in range(n+1)]
dp[0][h] = 0
for i in range(n):
    for j in range(h, -1, -1):
        dp[i+1][j] = dp[i][j]
        if j + dat[i][0] <= h:
            dp[i+1][j] = min([dp[i+1][j], dp[i+1][j+dat[i][0]]+dat[i][1]])
        if j == 0:
            for k in range(1, min([h, dat[i][0]])+1):
                dp[i+1][j] = min([dp[i+1][j], dp[i+1][k] + dat[i][1]])
print(dp[n][0])

Solution (Python):

import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  
AB = [tuple(map(int, input().split())) for _ in range(n)]

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

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

print(dp(h))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(answer, dp[i] + b)

print(answer)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

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

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

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



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

for i in range(0, N):
    for j in range(1, H+1):        
        dp[i+1][j] = min(dp[i][j], dp[i+1][max(0, j-A[i])] + B[i])
        
print(int(dp[-1][-1]))

Solution (Python):
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    dp = [inf]*(H+1)
    dp[0] = 0
    ans = inf
    for j in range(N):
        a,b = A[j],B[j]
        for i in range(H+1-a):
            dp[i + a] = min(dp[i + a], dp[i] + b)
        for i in range(min(a + 1, H + 1)):
            dp[H] = min(dp[H], dp[H-i] + b)
    ans = dp[H]
    print(ans)
    return

def examF():
    class segment_():
        def __init__(self, A, n, segfunc):
            
            self.ide_ele = 0
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        
        def update_add(self, k,u):
            k += self.num
            self.seg[k] += u
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    B = [0] * (N + 1)
    S = segment_(B,(N+1),lambda a, b: a+b)
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        left = bisect.bisect_left(X,X[i]-D*2)

        cur -= min(S.query(left,i),cur)
        ans +=cur
        S.update_add(i,cur)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

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

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

ans = dp[H]
for i in range(H, H+max(A)+1):
    ans = min(ans, dp[i])
print(ans)

Solution (Python):
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 else float('inf') for a, b in magic]

    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)

Solution (Python):
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)

Solution (Python):
H,N = map(int,input().split())

data = []

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

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    
print(dp[H])

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    h,n=map(int,input().split())
    m=0
    AB=[]
    for _ in range(n):
        a,b=map(int,input().split())
        AB.append((a,b))
        m=max(m,a)
    DP=[float('inf')]*(h+m+1)
    DP[0]=0
    for i in range(h+m):
        for a,b in AB:
            if i-a<0:
                continue
            DP[i]=min(DP[i],DP[i-a]+b)
    print(min(DP[h:]))
    
if __name__=='__main__':
    main()

Solution (Python):
H, N = map(int, input().split())
ls = []
m = 0
for i in range(N):
  a, b = map(int,input().split())
  ls += [(a,b)]
  if m<a:
    m = a
dp = [float('inf')]*(H+m+1)
dp[0] = 0
L = H+m+1
ans = float('inf')
for i in range(1,L):
  for j in range(N):
    a, b = ls[j]
    if i-a>=0:
      dp[i] = min(dp[i-a]+b, dp[i])
    if i>=H:
      if ans>dp[i]:
        ans = dp[i]
print(ans)

Solution (Python):
"""
https://atcoder.jp/contests/abc153/tasks/abc153_e

個数制限なしDP
一次元の配列を使うパターン。
"""

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)

INF = float('INF')
MAX_J = 10 ** 4 + 1


DP = [INF] * MAX_J
DP[0] = 0



for i in range(N):
    for j in range(MAX_J):
        
        
        nj = min(j+A[i], H)
        
        DP[nj] = min(DP[nj], DP[j] + B[i])

print(DP[H])

Solution (Python):
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
 
max_a=max(a for a,_ in ab)
dp = [0] * (h+max_a)
 
for i in range(0,h+max_a):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[h])

Solution (Python):
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


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])

Solution (Python):
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 = [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])

Solution (Python):
import sys

input = sys.stdin.readline

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

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))