Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])


Fixed submission:
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != float('inf'):
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])


Fixed submission:
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

Fixed submission:
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])


Fixed submission:
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

Fixed submission:
import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])