Buggy python submission (verdict: Time Limit Exceeded):
import sys


def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == '__main__':
    print(resolve())


Fixed submission:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))


Fixed submission:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10 ** 20
dp = [[INF]*(H+10**4) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    a, b = next(AB)
    for j in range(H+10**4):
        dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b if j-a >= 0 else INF)
print(min(dp[-1][H:]))


Fixed submission:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = float('inf')
dp = [[INF]*(H+10**4) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    a, b = next(AB)
    for j in range(H+10**4):
        dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b if j-a >= 0 else INF)
# print(min([min(i[H:]) for i in dp]))
print(min(dp[-1][H:]))


Fixed submission:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = float('inf')
dp = [[INF]*(H+10**4) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    a, b = next(AB)
    for j in range(H+10**4):
        dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b if j-a >= 0 else INF)
print(min([min(i[H:]) for i in dp]))


Fixed submission:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))