Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+AB[j][1] < dp[i+AB[j][0]]:
                    dp[i+AB[j][0]] = dp[i]+AB[j][1]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = AB[j][1]
                tmp3 = AB[j][0]
                if tmp1+tmp2 < dp[i+tmp3]:
                    dp[i+tmp3] = tmp1+tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    INF = float('inf')
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    for i in range(N):
        if i == 0:
            dp[i] = 0
        for j in range(AB[i][0],H+maxA):
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    INF = float('inf')
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA+1)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = tmp1 + B[j]
                if tmp2 < dp[i+A[j]]:
                    dp[i+A[j]] = tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+B[j] < dp[i+A[j]]:
                    dp[i+A[j]] = dp[i]+B[j]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+B[j] < dp[i+A[j]]:
                    dp[i+A[j]] = dp[i]+B[j]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A))
    dp[0] = 0
    for i in range(N):
        for j in range(A[i],H+max(A)):
            dp[j] = min(dp[j],dp[j-A[i]]+B[i])
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()