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

sys.setrecursionlimit(500000)
h, n = 0, 0
ab = None
dp = dict()

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

def main():
    global h, n, ab
    h, n = map(int, input().split())
    ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
    print(f(n - 1, h))

if __name__ == "__main__":
  main()

Fixed submission:
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))

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

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Fixed submission:
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))

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

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    if (i, j) not in dp:
        dp[(i, j)] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[(i, j)]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Fixed submission:
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))

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

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    if dp.get((i, j)) is None:
        dp[(i, j)] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[(i, j)]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Fixed submission:
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))