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

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    AB = [None] * N
    for i in range(N):
        AB[i] = tuple(map(int, input().split()))

    INF = 10 ** 18
    dp = [INF] * (H + 1)
    dp[0] = 0
    for A, B in AB:
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

import numpy as np

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = np.zeros(N, dtype=np.int32)
    B = np.zeros(N, dtype=np.int32)
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = np.full(H + max(A), 10**8, dtype=np.int32)
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

INF = float("inf")


def main():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    max_A = max(A)
    dp = [float("inf")] * (H + max_A)
    dp[0] = 0
    for h in range(1, H + max_A):
        dp[h] = min(dp[max(0, h-a)]+b for a, b in zip(A, B))
    ans = min(dp[H:])
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [float("inf")] * (H + 1 + max(A) - 1)
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

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

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [float("inf")] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            next_h = min(H, h+a)
            dp[next_h] = min(dp[next_h], dp[h]+b)
    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()