Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print(min(DP[H:]))


Fixed submission:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))
AB.sort()

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print(min(DP[H:]))


Fixed submission:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))


Fixed submission:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))


Fixed submission:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2* 10**4+1)]
DP[0] = 0
for i in range(10**4):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))


Fixed submission:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))