Problem: 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.

Submission attempts (in order):
import math import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(H-A+1,H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B

    dp=ndp
    print(dp)

print(dp[-1])

import math
import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        if ndp[-1]==None:
            pass
        elif j >=H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

        ndp[j]=min(ndp[j-A]+B,dp[j])

    if A >= H and dp[-1]!=None:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])

import math

def main():
    H,N=map(int,input().split())

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

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

                if j > H-A:
                    
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B
        print(dp)

    print(dp[-1])

main()

import math

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

amax=max(A_list)

inf=float('inf')
dp=np.array([0]+[inf]*(H+amax))

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B
    
    minA=np.amin(dp[H-A:])+B
    if minA < dp[-1]:
        dp[-1]=minA

print(dp[-1]))


import math
import copy

def main():
    H,N=map(int,input().split())

    #inf=float('inf')
    dp=[0]+[1e8]*H

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

                if j > H-A:
                    
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()

import math
import copy
H,N=map(int,input().split())

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

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    dp=ndp
    if A>=H:
        ndp[-1]=min(B,dp[-1])

print(dp[-1])


import math
import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    #for j in range(H-A+1,H+1):
    #    if ndp[j]==None:
    #        continue

    #    if ndp[-1]!=None:
    #        ndp[-1]=min(ndp[j]+B,ndp[-1])
    #    else:
    #        ndp[-1]=ndp[j]+B

    dp=ndp

print(dp[-1])

import math
import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if ndp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if ndp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(H-A+1,H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B

    dp=ndp

print(dp[-1])

import math
import copy
H,N=map(int,input().split())

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

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    dp=ndp

print(dp[-1])

import math

def main():
    H,N=map(int,input().split())

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

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

                if j > H-A:
                    
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted