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
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=[math.inf]*(H+max(A)-1)

for Ai in A:
    DP[Ai-1]=Ai 

for dpi in range(H+max(A)-1):
    kouho=[]
    for Ai,Bi in zip(A,B):
        kouho.append(DP[dpi])
        if dpi-Ai>=0:
            kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=min(kouho)


print(min(DP[H-1:]))

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=[10**9]*(H+max(A)-1)

for Ai in zip(A,B):
    DP[Ai-1]=Bi

for dpi in range(H+max(A)-1):
    kouho=[]
    kouho.append(DP[dpi])
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=min(kouho)


print(min(DP[H-1:]))

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:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))


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:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:])



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=[10**9]*(H+max(A)-1)

for Ai,Bi in zip(A,B):
    DP[Ai-1]=Bi

for dpi in range(H+max(A)-1):
    
    
    kouho=DP[dpi]
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            if kouho<DP[dpi-Ai]+Bi
            
    DP[dpi]=kouho


print(min(DP[H-1:]))

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

max_a=max(a for a,_ in ab)

for i in range(0,h+max_a):
    if i==0:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:])


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=[10**9]*(H+max(A)-1)

for Ai in A:
    DP[Ai-1]=Ai 

for dpi in range(H+max(A)-1):
    kouho=[]
    kouho.append(DP[dpi])
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=min(kouho)


print(min(DP[H-1:]))

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

max_a=max(a for a,_ in ab)

for i in range(0,h+max_a):
    if i==0:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:])


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=[10**9]*(H+max(A)-1)

for Ai in A:
    DP[Ai-1]=Ai 

for dpi in range(H+max(A)-1):
    kouho=[]
    for Ai,Bi in zip(A,B):
        kouho.append(DP[dpi])
        if dpi-Ai>=0:
            kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=min(kouho)


print(min(DP[H-1:]))

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=[10**9]*(H+max(A)-1)

for Ai,Bi in zip(A,B):
    DP[Ai-1]=Bi

for dpi in range(H+max(A)-1):
    
    
    kouho=DP[dpi]
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            if kouho<DP[dpi-Ai]+Bi:
            
    DP[dpi]=kouho


print(min(DP[H-1:]))

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

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Accepted