Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Fixed submission:
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = 1e9
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for magic  in MAGICS:
        DP[h] = min(DP[max(h - magic[0], 0)] + magic[1], DP[h])

print(DP[H])

Fixed submission:
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for (damage, mp)  in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Fixed submission:
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for j, magic in enumerate(MAGICS):
        (damage, mp) = magic
        DP[h] = min(DP[max(h - damage, 0)]+mp, DP[h])

print(DP[H])


Fixed submission:
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+MAX+1)]

DP[0] = 0

for h in range(H+1):
    for j, magic in enumerate(MAGICS):
        (damage, mp) = magic
        DP[h + damage] = min(DP[h + damage], DP[h] + mp)

for i in reversed(range(len(DP))):
    DP[i-1] = min(DP[i], DP[i-1])

print(DP[H])


Fixed submission:
import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])