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):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * (MAX_LEN * (n + 1))
dp[0] = 0
ans = INF
for i in range(1, n+1):
    v, w = ab[i-1]
    offset = i * MAX_LEN
    offset_before = offset - MAX_LEN
    for j in range(h+1):
        if j < v:
            dp[offset+j] = dp[offset_before+j]
        elif dp[offset_before+j] > dp[offset+j-v] + w:
            if j >= h and ans > dp[offset+j-v] + w:
                ans = dp[offset+j-v] + w
            else:
                dp[offset+j] = dp[offset+j-v] + w
        else:
            dp[offset+j] = dp[offset_before+j]
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
    v, w = ab[i-1]
    for j in range(h+1):
        if dp[i+1][j] > dp[i][j]:
            dp[i+1][j] = dp[i][j]
        dp[i+1][j+v] = dp[i+1][j] + w
ans = min(dp[n][h:])
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4
 
h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(1, n+1):
    v, w = ab[i-1]
    for j in range(h+1):
        if dp[j] > dp[j-v] + w:
            dp[j] = dp[j-v] + w
ans = min(dp[h:])
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
    v, w = ab[i]
    for j in range(10**4):
        if dp[i][j] == INF:
            continue
        dp[i][j+v] = dp[i][j] + w
        dp[i+1][j + v] = dp[i][j] + w
        if dp[i+1][j] > dp[i][j]:
            dp[i+1][j] = dp[i][j]
ans = min(dp[n][h:])
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted