Buggy python submission (verdict: Time Limit Exceeded):
# Problem E - Crested Ibis vs Monster

# input
H, N = map(int, input().split())
ab_pattern = []
for i in range(N):
    a, b = map(int, input().split())
    ab_pattern.append([a, b])

# initialization
mp_list = [float('INF')] * (H+1)
mp_list[0] = 0

# dp
for i in range(1, H+1):
    for ab in ab_pattern:
        a = ab[0]
        b = ab[1]
        if i-a>=0:
            mp_list[i] = min(mp_list[i], mp_list[i-a] + b)
        else:
            mp_list[i] = min(mp_list[i], mp_list[0] + b)

# output
print(mp_list[H])


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Buggy python submission (verdict: Time Limit Exceeded):
# Problem E - Crested Ibis vs Monster

# input
H, N = map(int, input().split())
ab_pattern = []
for i in range(N):
    a, b = map(int, input().split())
    ab_pattern.append([a, b])

# initialization
mp_list = [float('INF')] * (H+1)
mp_list[0] = 0

# dp
for i in range(1, H+1):
    for ab in ab_pattern:
        a = ab[0]
        b = ab[1]
        if i-a>=0:
            mp_list[i] = min(mp_list[i], mp_list[i-a] + b)
        else:
            mp_list[i] = min(mp_list[i], mp_list[0] + b)

# output
print(mp_list[H])


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Buggy python submission (verdict: Time Limit Exceeded):
# ダイナミック・プログラミング

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Buggy python submission (verdict: Time Limit Exceeded):
# ダイナミック・プログラミング

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

def chmin(a, b):
    if a>=b:
        return b
    else:
        return a

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        dp[i+1][j] = chmin(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+A[i],H)] = chmin(dp[i+1][min(j+A[i],H)], dp[i+1][j]+B[i])

print(dp[N][H])


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Buggy python submission (verdict: Runtime Error):
# ダイナミック・プログラミング(DP)

H, N = map(int, input().split())
magic_list = []

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


dp_memo = {} # メモ化再帰
def dp_magic_2(HP):
    mp_list = []
    if HP<=0:
        return 0
    elif HP in dp_memo:
        return dp_memo[HP]
    else:
        for m in magic_list:
            mp_list.append(dp_magic_2(HP-m[0]) + m[1])
        result_mp = sorted(mp_list)[0]
        dp_memo[HP] = result_mp
        return result_mp

print(dp_magic_2(H))


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Buggy python submission (verdict: Runtime Error):
# ダイナミック・プログラミング(DP)

H, N = map(int, input().split())
magic_list = []

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


dp_memo = {} # メモ化再帰
def dp_magic_2(HP):
    mp_list = []
    if HP<=0:
        return 0
    elif HP in dp_memo:
        return dp_memo[HP]
    else:
        for m in magic_list:
            mp_list.append(dp_magic_2(HP-m[0]) + m[1])
        result_mp = min(mp_list)
        dp_memo[HP] = result_mp
        return result_mp

print(dp_magic_2(H))


Fixed submission:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])