Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for a,b in lst:
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for a,b in lst:
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):

h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)


Fixed submission:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)