Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**10
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for a,b in x:
        for i in range(a,H+ma+1):
            if dp[i-a] != INF:
                dp[i] = min(dp[i],dp[i-a]+b)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for i in range(1,H+ma+1):
        dp[i] = min(dp[i-a]+b for a,b in x)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    H,N = map(int,input().split())
    INF = 10**10
    at = []
    for _ in range(N):
        A,B = map(int,input().split())
        at.append((A,B))
        
    at.sort(key=itemgetter(0))
    
    dp = [INF for _ in range(H+1)]
    dp[0] = 0
    for i in range(N):
        use,a = at[i]
        for j in range(1,H+1):
            if j < use:
                dp[j] = min(dp[j],a)
            else:
                dp[j] = min(dp[j],dp[j-use]+a)
        
    print(dp[-1])
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for i in range(1,H+ma+1):
        dp[i] = min(dp[i-a]+b for a,b in x)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    H,N = map(int,input().split())
    INF = 10**10
    at = []
    for _ in range(N):
        A,B = map(int,input().split())
        at.append((A,B))
        
    at.sort(key=itemgetter(0))
    
    dp = [INF for _ in range(H+1)]
    dp[0] = 0
    for i in range(N):
        use,a = at[i]
        for j in range(1,H+1):
            if j < use:
                dp[j] = min(dp[j],a)
            else:
                dp[j] = min(dp[j],dp[j-use]+a)
        
    print(dp[-1])
    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for i in range(1,H+ma+1):
        dp[i] = min(dp[i-a]+b for a,b in x)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()