Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

Fixed submission:
h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

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

h, n = map(int, input().split())
magic = []
INF = 10 ** 9
for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))
ans = 0
dp = [float('inf')] * (h + 1)

sys.setrecursionlimit(10 ** 7)
# 入力: 体力, 出力: 魔力の最小値
def magic_cost(hp):
    if dp[hp] != float('inf'):
        return dp[hp]

    cost_min = float('inf')
    for a, b in magic:
        if a >= hp:
            cost = b
        else:
            cost = b + magic_cost(hp - a)
        cost_min = min(cost, cost_min)
    dp[hp] = cost_min
    return cost_min

print(magic_cost(h))

Fixed submission:
h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

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

h, n = map(int, input().split())
magic = []
INF = 10 ** 9
for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))
ans = 0
dp = [float('inf')] * (h + 1)

sys.setrecursionlimit(10 ** 7)
# 入力: 体力, 出力: 魔力の最小値
def magic_cost(hp):
    if dp[hp] != float('inf'):
        return dp[hp]

    cost_min = float('inf')
    for a, b in magic:
        if a >= hp:
            cost = b
        else:
            cost = b + magic_cost(hp - a)
        cost_min = min(cost, cost_min)
    dp[hp] = cost_min
    return cost_min

print(magic_cost(h))

Fixed submission:
h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
magic = []
INF = 10 ** 9
for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))
ans = 0
dp = [float('inf')] * (h + 1)

# 入力: 体力, 出力: 魔力の最小値
def magic_cost(hp):
    if dp[hp] != float('inf'):
        return dp[hp]

    cost_min = float('inf')
    for a, b in magic:
        if a >= hp:
            cost = b
        else:
            cost = b + magic_cost(hp - a)
        cost_min = min(cost, cost_min)
    dp[hp] = cost_min
    return cost_min

print(magic_cost(h))


Fixed submission:
h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))