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):
    dp[i]=np.min(dp[np.maximum(i-ab[:, 0],0)]+ab[:,1])
print(dp[-1])

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):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
print(dp[-1])

Solution (Python):


"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


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):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    
print(dp[-1])

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

INF = 10 ** 18

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

dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        if j < A:
            dp[j] = min(dp[j], dp[0] + B)
        else:
            dp[j] = min(dp[j], dp[j - A] + B)
    
print (dp[H])

Solution (Python):
INF = 10 ** 18


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

dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    
print (dp[N][H])

Solution (Python):
h, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
maxa = max(a for a,b in ab)
dp = [0 for i in range(h+maxa)]
for i in range(1, h+maxa):
    dp[i] = min(dp[i - a]+b for a,b in ab)
print(min(dp[h:]))

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


def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    H, N = map(int, input().split())
    magics = tuple(readlines(N))
    INF = 10**9
    dp = [INF]*(H+10**4+1)
    dp[0] = 0
    for a, b in magics:
        for i in range(H):
            if dp[i] != INF:
                t = dp[i] + b
                if t < dp[i+a]:
                    dp[i+a] = t
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

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

h,n=map(int, readline().split())
l=[list(map(int, readline().split())) for _ in range(n)]

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

for i in range(h):
    for a, b in l:
        x=i+a
        if x>h:
            x=h
        y=dp[i]+b
        if y<dp[x]:
            dp[x]=y

print(dp[h])

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

print(dp[h])

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




dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])

Solution (Python):
INF = 10**9
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 = [INF] * (h + 1)
dp[0] = 0
for i in range(n):
    for j in range(h + 1):
        m = min(h, j + a[i])
        dp[m] = min(dp[m], dp[j] + b[i])
print(dp[h])

Solution (Python):
H, N = map(int, input().split())
inf = 1 << 32
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    a,b = map(int, input().split())
    for j in range(H+1):
        dp[min(H,j + a)] = min(dp[min(H,j + a)], dp[j] + b)
print(dp[H])

Solution (Python):
import numpy as np

H,N = map(int,input().split())
S=[None for i in range(N)]
for i in range(N):
  S[i] = list(map(int,input().split()))
S = np.array(S)

dp = np.zeros(H+1)
for i in range(1,H+1):
  dp[i] = min(dp[np.maximum(0, i-S[:,0])]+S[:,1])

print(int(dp[-1]))

Solution (Python):
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)
 
inf = float("inf")
dp = [inf] * (H+maxA+1)
dp[0] = 0
 
for j in range(N):
    for i in range(a[j], H+maxA+1):
        dp[i] = min(dp[i], dp[i-a[j]]+b[j])
 
print(min(dp[H:]))

Solution (Python):


def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

Solution (Python):
h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

for i in range(1, hmaxa):
    ab_child = [dp[i-a]+b for a,b in ab]
    dp[i] = min(ab_child)

print(min(dp[h:]))

Solution (Python):
h, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
maxa = max(a for a,b in ab)
dp = [0 for i in range(h+maxa)]
for i in range(1, h+maxa):
    dp[i] = min(dp[i - a]+b for a,b in ab)
print(min(dp[h:]))

Solution (Python):
import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for i in range(1, H + max_damage):
    dp[i] = min(dp[i - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)

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 = [0 for i in range(H+1)]

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

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

DP = [float('inf')]*(H+1)  

DP[-1] = 0
for i in reversed(range(H+1)):
    for a, b in L:
        if i-a >= 0:
            DP[i-a] = min(DP[i] + b, DP[i-a])
        else:
            DP[0] = min(DP[0], DP[i]+b)
print(DP[0])

Solution (Python):
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
  ai, bi = map(int, input().split())
  A.append(ai)
  B.append(bi)

A = np.array(A)
B = np.array(B)

dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)


print(dp[H])

Solution (Python):
import sys
import numpy as np
 
h, n = map(int, input().split())
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]
 
dp = np.zeros(10001, dtype=np.int64)






for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print(dp[h])

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

weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=l[i][0],l[i][1]
w=h

dp=[[float('inf')]*(w+1) for i in range(n+1)]
for i in range(n):
    for j in range(1,h+1):
        if j<=weight[i]:
            dp[i+1][j]=min(dp[i][j],value[i])
        elif j>=weight[i]:
            dp[i+1][j]=min(dp[i+1][j-weight[i]]+value[i],dp[i][j])
    
print(dp[n][w])

Solution (Python):
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(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):
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)

dp=[float("inf")]*(2*10000+1)
dp[0]=0

for i in range(h):
    for j in range(n):
        if (i+a[j])>2*10000:
            dp[2*10000]=min(dp[2*10000],dp[i]+b[j])
            continue
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])

ans=float("inf")
for j in range(h,2*10000+1):
    ans=min(ans,dp[j])
print(ans)

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for a in range(n)]
dp=[inf]*(h+1)
dp[0]=0

for a in range(1,n+1):
    for b in range(0,h+1):
        key=min(h,b+AB[a-1][0])
        dp[key]=min(dp[key],dp[b]+AB[a-1][1])
print(dp[h])

Solution (Python):
import numpy as np


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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T


dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)


print(dp[H])

Solution (Python):
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)

inf = float("inf")
dp = [inf] * (H+maxA+1)
dp[0] = 0

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

print(min(dp[H:]))

Solution (Python):
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)

inf = float("inf")
dp = [inf for _ in range(H+maxA+1)]
dp[0] = 0

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

print(min(dp[H:]))

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

for i in range(h + 1):
    for damage, mp in ab:
        rep = INF
        if (0 <= (i - damage)):
            rep = dp[i - damage] + mp
        else:
            rep = mp
        dp[i] = min(dp[i], rep)
print(dp[h])

Solution (Python):
H,N = map(int,input().split())
magic = []
for i in range(N):
  a,b = map(int,input().split())
  magic.append((a,b))
A = [item[0] for item in magic]
maxA = max(A)
minA = min(A)
dp = [float("inf")]*(H+maxA+1)
dp[0]=0
for i in range(H+maxA):
  for j in range(N):
    dp[i] = min(dp[i],
                dp[max(i-magic[j][0],0)]+magic[j][1])
print(dp[H])

Solution (Python):
import numpy as np

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

A = np.array(A)
B = np.array(B)

dp = np.full(H + 1, np.inf)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

print(int(dp[H]))

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for a in range(n)]
dp=[[inf for b in range(h+1)] for a in range(n+1)]
dp[0][0]=0

for a in range(1,n+1):
    for b in range(0,h+1):
        dp[a][b]=min(dp[a][b],dp[a-1][b])
        key=min(h,b+AB[a-1][0])
        dp[a][key]=min(dp[a][key],dp[a][b]+AB[a-1][1])
print(dp[n][h])

Solution (Python):









h, n = map(int, input().split())
dp=[10**8]*(10**5+1)

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

for i in range(1,h+1):
  for j in range(0,n):
    if i-ab[j][0]<=0:
      x=ab[j][1]
    else:
      x=dp[i-ab[j][0]]+ab[j][1]
    dp[i]=min(dp[i],x)
print(dp[h])

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

A, B = [0] * N, [0] * N

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

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

for i in range(N):
    for j in range(H+1):
        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())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())


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

answer = min(dp[H:(H+M+1)])
print(answer)

Solution (Python):
INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [0] + [INT_MAX]* h
for i in range(1, h+1):
  v = INT_MAX
  for a, b in e:
    c = dp[max(0, i - a)] + b
    v = min(v, c)
  dp[i] = v
print(dp[h])

Solution (Python):
INT_MAX = 10**8
h, n = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(n)]

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

print(dp[h])

Solution (Python):
INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

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

print(dp[h])

Solution (Python):
H,N=map(int, input().split())
A=[list(map(int, input().split())) for i in range(N)]
maxa=max(a for a,b in A)
DP=[0]*(H+maxa)
for i in range(0,H+maxa):
  if i<=0:
    DP[i]=0
  else:
    DP[i]=min(DP[i-a]+b for a,b in A)
print(min(DP[H:]))

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_max = 10000000000
dp = [dp_max for i in range(H+1)]

dp[0] = 0
 
for i in range(H+1):
  if dp[i] == dp_max:
    continue
 
  for j in range(N):
    ni = min(H, i + A[j])
 
    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

Solution (Python):
h,n = map(int,input().split())
dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg + a)
ba.sort()

d = [10**9]*(h+1)
d[0] = 0

for i in range(1, h+1):
    for e in ba:
        a,b = e%dg, e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b
print(d[-1])

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=[1000000000]*(H+max(A)+1)
DP[0]=0


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

for i in range(N):
    for h in range(A[i],H+max(A)+1):
        DP[h]=min(DP[h-A[i]]+B[i],DP[h])

print(min(DP[H:]))

Solution (Python):
import sys

H, N = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]







INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + M[j][0])
        b = M[j][1]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])

Solution (Python):
import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

dp = np.array([0]*(H+1))

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)

print(dp[-1])

Solution (Python):
def knapsack(N,W,weight,value):
  
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: 
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))

Solution (Python):
H,N,*AB = map(int, open(0).read().split())
dp = [0]+[10**8]*H
for n in range(N):
  A,B = AB[2*n:2*(n+1)]
  for h in range(1,H+1): dp[h] = min(dp[h],dp[max(0,h-A)]+B)
print(dp[-1])

Solution (Python):
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == inf:
            continue
        t1 = dp[i]
        for a, b in AB:
            t2 = t1 + b
            if t2 < dp[i + a]:
                dp[i + a] = t2
    print(min(dp[H:]))


main()

Solution (Python):
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    inf = float('inf')
    dp = [inf] * (H + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == inf:
            continue
        t1 = dp[i]
        for a, b in AB:
            t2 = i + a
            if t2 > H:
                t2 = H
            t3 = t1 + b
            if t3 < dp[t2]:
                dp[t2] = t3
    print(dp[H])


main()

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for _ in range(N):
    A, B = map(int, input().split())
    for i in range(H):
        t1 = i + A
        if t1 > H:
            t1 = H
        t2 = dp[i]
        if t2 == inf:
            continue
        t2 += B
        if t2 < dp[t1]:
            dp[t1] = t2
print(dp[H])

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for _ in range(N):
    A, B = map(int, input().split())
    for i in range(H):
        t1 = i + A
        if t1 > H:
            t1 = H
        t2 = dp[i] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print(dp[H])

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = map(int, input().split())
    for j in range(H):
        t1 = j + A
        if t1 > H:
            t1 = H
        t2 = dp[j] + B
        if t2 < dp[t1]:
            dp[t1] = t2
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)
inf = float('inf')
dp = [inf] * (H + max_A + 1)
dp[0] = 0
for i in range(1, H + max_A + 1):
    for a, b in AB:
        t1 = i - a
        if t1 < 0:
            continue
        t2 = dp[t1]
        if t2 == inf:
            continue
        if t2 + b < dp[i]:
            dp[i] = t2 + b
print(min(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(min(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(min(dp[h:]))

Solution (Python):
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

H,N = LI()
A = []
B = []
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

dp = [inf]*(H+1)
ans = inf

dp[H] = 0

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

Solution (Python):
H,N = map(int,input().split())
spells = [tuple(map(int,input().split())) for _ in range(N)]
max_a = max(spells)[0]

dp = [0]
for i in range(1, H + max_a + 1):
  try:
    dp.append(min([dp[i - a] + b for a,b in spells if a <= i]))
  except ValueError:
    dp.append(10**8)

print(min(dp[H:]))

Solution (Python):
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == inf:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Solution (Python):
import math
 
h,n=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=[[b[0]] * (h+1) for i in range(n+1)]
for j in range(h+1):
    dp[0][j]=math.ceil(j/a[0])*b[0]
for i in range(n):
    for j in range(h+1):
        if j<a[i]: 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])

Solution (Python):
def main():
    h, n = map(int, input().split())
    ab = []
    for i in range(n):
        ab.append(tuple(map(int, input().split())))

    dp = []
    for i in range(h+1):
        dp.append(10**18)
    dp[h] = 0
    for i in range(h, 0, -1):
        for j in range(n):
            dp[max(0, i-ab[j][0])] = min(dp[max(0, i - ab[j][0])], dp[i] + ab[j][1])

    print(dp[0])


if __name__ == '__main__':
    main()

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

max_v = 10100
x = float("inf")

dp = [x] * max_v

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

ans = x
for i in range(max_v):
    if i >= h:
        ans = min(ans, dp[i])

print(ans)

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

a_max = 10000
dp_max = 100000000
dp = [dp_max] * (h + a_max + 1)
dp[0] = 0

for i in range(h):
    if dp[i] == dp_max:
        continue
    for j in range(n):
        a_current = a[j]
        b_current = b[j]
        if dp[i] + b_current < dp[i + a_current]:
            dp[i + a_current] = dp[i] + b_current

dp_min = dp_max
for i in range(h, h + a_max + 1):
    if dp[i] < dp_min:
        dp_min = dp[i]

print(dp_min)

Solution (Python):
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))

Solution (Python):
H, N = map(int, input().split())
INF = 10 ** 12

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

dp = [INF for j in range(H+10**4+1)]
dp[0] = 0

for i in range(N):
    for j in range(1, H+10**4+1):
        if j - M[i][0] >= 0:
            dp[j] = min(dp[j], dp[j-M[i][0]] + M[i][1])

ans = INF
for i in range(10**4+1):
    ans = min(ans, dp[H+i])
print(ans)

Solution (Python):



def main():
    h, n = map(int, input().split(" "))
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        damage, cost = map(int, input().split(" "))
        for total in range(h +1):
            
            next_damage = min(total + damage, h)
            dp[next_damage] = min(dp[next_damage], dp[total] + cost)
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [[INF] * (H+1) for i in range(N+1)]

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

    
    
    print(dp[N][H])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
h,n = map(int,input().split())
a=[0]*n
b=[0]*n

MAX_HP = 10**4
MAX_HP = h
for i in range(n):
  ta,tb = map(int,input().split())
  a[i] = ta
  b[i] = tb

INF = 10**9

dp = [[INF]*(h+1) for _ 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[-1][-1])

Solution (Python):
s = input().rstrip().split(' ')
h = int(s[0])
n= int(s[1])

A = []
B = []

for i in range(n):
    AB = list(map(int, input().rstrip().split(' ')))
    A.append(AB[0])
    B.append(AB[1])

dp = [[float('inf')] * (h+1)] * (n+1)
dp[0][0] = 0

def min(a, b):
    if a < b:
        return a
    else:
        return b

for i in range(n):
    for j in range(h):
        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):
import numpy as np


def inpl():
    return list(map(int, input().split()))


H, N = inpl()
AB = [inpl() for i in range(N)]

A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

dp = np.zeros(H + 1, dtype=np.int64)
for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

print(dp[H])

Solution (Python):
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)

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

dp = [[10 ** 9] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i, (a, b) in enumerate(X):
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][min(j + a, H)] = min(dp[i + 1][min(j + a, H)], dp[i + 1][j] + b)

print(dp[-1][-1])

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

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

if __name__=='__main__':
	main()