Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [a for a, b in AB]
B = [b for a, b in AB]
inf = 10**10
# DP[i][j]=i個以内で体力j以上削るための消費魔力の最小値
DP = [[inf for j in range(h+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    for j in range(h+1):
        DP[i][j] = min(DP[i-1][j], DP[i][max(0, j-A[i-1])]+B[i-1])
print(DP[n][h])


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
A, B = [], []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
F = [0]
for i in range(1, h+1):
    f = 1 << 30
    for a, b in zip(A, B):
        if i < a:
            f = min(f, b)
        else:
            f = min(f, F[i-a]+b)
    F.append(f)
print(f)


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for n in range(N):
    for h in range(H):
        if dp[h] == inf:
            continue
        dp[h + A[n]] = min(dp[h + A[n]], dp[h] + B[n])
print(min(dp[H:]))


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [[0 for h in range(H+1)] for n in range(N+1)]
# dp[n][h]は0~n-1の魔法で体力hを削るのに使う魔力
dp[0] = [0] + [inf for h in range(1, H+1)]
for n in range(1, N+1):
    for h in range(H+1):
        dp[n][h] = min(dp[n - 1][h], dp[n][max(0, h - A[n - 1])] + B[n - 1])
print(dp[N][H])


Fixed submission:
inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()