Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

AB.sort(key=lambda x: x[1]/x[0])

cost = [(float('inf'),float('inf'))]*(H+1)
last = [0]*(H+1)

q = [((0,0), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break

    c,li = cli
    for i,(a,b) in enumerate(AB[li:], start=li):
        d = min2(H,t+a)
        if cost[d] > (c+b,i):
            heappush(q, ((c+b, i), d))

print(cost[H][0])


Fixed submission:
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

AB.sort(key=lambda x: -x[1])

cost = [float('inf')]*(H+1)
last = [None]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if cost[t] <= c:
        continue
    cost[t] = c
    if t == H:
        break
    if last[t] is None:
        for i,(a,b) in enumerate(AB):
            d = min2(H,t+a)
            if cost[d] > c+b:
                last[d] = i
                heappush(q, (c+b, d))
            if cost[d] == c+b:
                last[d] = min2(last[d], i)
    else:
        for i,(a,b) in enumerate(AB[last[t]:]):
            d = min2(H,t+a)
            if cost[d] > c+b:
                last[d] = i
                heappush(q, (c+b, d))
            if cost[d] == c+b:
                last[d] = min2(last[d], i)

print(cost[H])


Fixed submission:
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

cost = [float('inf')]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if cost[t] <= c:
        continue
    cost[t] = c
    if t == H:
        break
    for a,b in AB:
        d = min(H,t+a)
        if cost[d] > c+b:
            heappush(q, (c+b, d))

print(cost[H])

Fixed submission:
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

cost = [float('inf')]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if t >= H:
        cost[H] = c
        break
    if cost[t] <= c:
        continue

    cost[t] = c
    for a,b in AB:
        heappush(q, (b+c, t+a))

print(cost[H])

Fixed submission:
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])