Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
dp = [ 0 for _ in range(H+1)]
dp[0] = 0
AB = [list(map(int, input().split())) for _ in range(N)]
for j in range(1, H+1):
  dp[j] = min([dp[max(0, j-a)] + b for a, b in AB])
print(dp[H])


Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

H, N = map(int, input().split())
#dp = [ float("inf") for _ in range(H+1)]
dp = np.array([float("inf")]*(H+1))
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

    
print(int(dp[H]))

Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

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

print(dp[H])

Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
for i in range(N):
  A[i], B[i] = map(int, input().split())

dplength = H+max(A)+1
INF = 100000000000
# dp[i] : 体力をi減らすための魔力の最小値
dp = [ INF for _ in range(dplength)]
dp[0] = 0
answer = INF
for i in range(dplength):
  for j in range(N):
    if A[j] <= i:
      dp[i] = min(dp[i], dp[i-A[j]] + B[j])
    else:
      dp[i] = min(dp[i], B[j])
  if H <= i:
    answer = min(answer, dp[i])

print(answer)

Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for a in range(N)]

A = [ab[0] for ab in AB]
B = [ab[1] for ab in AB]

INF = 100000000000
# dp[i] : 体力をi減らすための魔力の最小値
dp = [ INF for _ in range(H+max(A)+1)]
dp[0] = 0

for i in range(H+max(A)+1):
  for j in range(N):
    if A[j] <= i:
      dp[i] = min(dp[i], dp[i-A[j]] + B[j])
    else:
      dp[i] = min(dp[i], B[j])

print(min(dp[H::H+max(A)+1]))

Fixed submission:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])