Problem p02787 (python)

Fixed submission:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    maxA = max(A)
    HmaxA = H + maxA
    minB = min(B)
    dp = [max(B) * HmaxA] * (HmaxA + 1)
    dp[0] = 0
    for h in range(HmaxA):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = h + A[n]
            if hp <= HmaxA:
                dp[hp] = min(dp[hp], dp[h] + B[n])
        print(h, dp)
    return min(dp[H:HmaxA+1])

print(ibis(H, A, B))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

import sys
sys.setrecursionlimit(max(1000, 2**N))

memo = [-1] * (H + 1)
def ibis(H):
    if memo[H] >= 0:
        return memo[H]
    if H <= 0:
        return 0
    mp = [0] * N
    for n in range(N):
        mp[n] = B[n] + ibis(H - A[n])
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

import sys
sys.setrecursionlimit(max(1000, H*N))

memo = [-1] * (H + 1)
def ibis(H):
    if memo[H] >= 0:
        return memo[H]
    if H <= 0:
        return 0
    mp = [0] * N
    for n in range(N):
        mp[n] = B[n] + ibis(H - A[n])
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

import sys
sys.setrecursionlimit(max(1000, H*N))

memo = [-1] * (H + 1)
def ibis(H):
    if memo[H] >= 0:
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

import sys
sys.setrecursionlimit(max(1000, H*N))

memo = [-1] * (H + 1)
def ibis(H):
    if memo[H] >= 0:
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

import sys
sys.setrecursionlimit(max(1000, H))

memo = dict()
def ibis(H):
    if H in memo.keys():
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

memo = dict()

def ibis(H):
    if H in memo.keys():
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

Buggy submission (verdict: Runtime Error):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

memo = [-1] * (H + 1)

def ibis(H):
    if memo[H] >= 0:
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))