Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if memo[hp] < 0:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [-1]*(H+1)
i = 0
while i <= H:
  solve(AB, i, memo)
  i += 1
print(memo[H])

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if not hp in memo:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = {}
for i in range(H+1):
  solve(AB, i, memo)
print(memo[H])

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0, -hp
  else:
    err = 0
    if not hp in memo:
      c_min = 10**10
      for attack, cost in ab:
        c, e = solve(ab, hp-attack, memo)
        if c+cost < c_min:
          c_min = c+cost
          err = e
      for i in range(err+1):
        memo[hp+i] = c_min
    return memo[hp], err

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
print(solve(AB, H, {})[0])

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if not hp in memo:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
print(solve(AB, H, {}))

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if not hp in memo:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
print(solve(AB, H, {}))

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])