Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
print(min(dp[h:]))


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for ab in AB: # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):

H, N = map(int, input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]

# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[-1])

Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        next_index = min(i + A[j], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        next_index = min(i + A[j], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(min(dp[h:]))


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 2)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(min(dp[h:]))


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])