Buggy python submission (verdict: Time Limit Exceeded):
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())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])

Fixed submission:
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())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[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())

a = [0] * n
b = [0] * n

for i in range(n):
    a[i], b[i] = map(int, input().split())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())

a = []
b = []

for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

dp = [pow(10, 10)] * (h + 1)
dp[0] = 0

for k in range(n):  # check magic
    for j in range(h):  # check dp
        next_index = min(j + a[k], h)
        dp[next_index] = min(dp[next_index], dp[j] + b[k])

print(dp[h])


Fixed submission:
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())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())

a = []
b = []

for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

dp = [pow(10, 10)] * (h + 1)
dp[0] = 0

for k in range(n):
    for j in range(h):
        if j + a[k] <= h and dp[j + a[k]] > dp[j] + b[k]:
            dp[j + a[k]] = dp[j] + b[k]
        elif j + a[k] > h:
            if dp[h] > dp[j] + b[k]:
                dp[h] = dp[j] + b[k]

print(dp[h])


Fixed submission:
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())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])