Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        if dp[start]==10**10:
            continue
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
h, n = map(int, input().split())
dp = np.array([10**10]*(h+1))
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

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

mins = [10**10]*(h+1)
mins[0] = 0
ind = 0
while ind < h:
    for a, b in magics:
        target = min(h, ind+a)
        mins[target] = min(b + mins[ind], mins[target])
    ind += 1
    while True:
        if mins[ind] < 10**10 and min(mins[ind:])==mins[ind]:
            break
        ind += 1
print(mins[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

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

mins = [None]*(h+1)
mins[0] = 0
ind = 0
while ind < h:
    for a, b in magics:
        target = min(h, ind+a)
        if mins[target] is None:
            mins[target] = b + mins[ind]
        else:
            mins[target] = min(b + mins[ind], mins[target])
    ind += 1
    while True:
        if mins[ind] is not None:
            break
        ind += 1
print(mins[h])


Fixed submission:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])