Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

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

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: (x[0], x[1]))

INF = 10**20
dp = [INF for i in range(H + 1)]
dp[0] = 0
for i in range(1, H + 1):
    if dp[i] != INF:
        continue
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp[i] = min_mp_cost
print(dp[-1])


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: (x[0], x[1]))

INF = 10**20
dp = [INF for i in range(H + 1)]
dp[0] = 0
for i in range(1, H + 1):
    if dp[i] != INF:
        continue
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = i - damage
        if parent <= 0:
            new_cost = mp_cost
        else:
            new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp[i] = min_mp_cost
print(dp[-1])


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: (x[0], x[1]))

cost = [-1 for i in range(H + 1)]


def f(H):
    c = []
    for damage, mp_cost in AB:
        tmp = H - damage
        if tmp <= 0:
            c.append(mp_cost)
            continue
            break
        if cost[tmp] != -1:
            c.append(cost[tmp] + mp_cost)
        else:
            cost[tmp] = f(tmp)
            c.append(cost[tmp] + mp_cost)
    return min(c)


# print('H', H)
# print('f(H)', f(H))
print(f(H))
# print('after cost', cost)


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

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

# AB = sorted(AB, key=lambda x: (-x[2], x[0]))
# print('AB', AB)

cost = [-1 for i in range(H + 1)]
# for damage, mp_cost in AB:
#     cost[damage] = mp_cost
# print('cost', cost)

# c = []
# for damage, mp_cost in AB:


def f(H):
    c = []
    for damage, mp_cost in AB:
        tmp = H - damage
        if tmp <= 0:
            c.append(mp_cost)
            continue
        if cost[tmp] != -1:
            c.append(cost[tmp] + mp_cost)
        else:
            cost[tmp] = f(tmp)
            c.append(cost[tmp] + mp_cost)
    return min(c)


# print('H', H)
# print('f(H)', f(H))
print(f(H))
# print('after cost', cost)


Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])