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

h, n = map(int, input().split())

INF = 10 ** 9

magic = []

for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))

# t = time.time()

magic.sort(reverse=True, key=lambda x: x[0])

dp = [INF] * (h + 10 ** 4)
dp[0] = 0
c = 0
for a, b in magic:
    for i in range(h):
        if dp[i] != INF:
            tmp = dp[i] + b
            c += 1
            if dp[i + a] > tmp:
                dp[i + a] = tmp

ans = min(dp[h:])

print(ans)
# print(time.time() - t)

Fixed submission:
def main():
    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:]))
 
 
main()

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

h, n = map(int, input().split())

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):
    if dp[i] == INF:
        continue
    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Fixed submission:
def main():
    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:]))
 
 
main()

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

h, n = map(int, input().split())

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):

    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)


Fixed submission:
def main():
    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:]))
 
 
main()

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

h, n = map(int, input().split())

INF = 10 ** 20

dp = collections.defaultdict(lambda : INF)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))



que = [0]
cc = [0]
m = 0
c = 0
while que:
    next_que = set()
    for now_dam in que:
        for a, b in magic:
            dam = now_dam + a
            if dp[dam] > dp[now_dam] + b:
                dp[dam] = dp[now_dam] + b
                if h > dam:
                    next_que.add(dam)
    que = list(next_que)
ans = INF

for k, v in dp.items():
    if k >= h:
        ans = min([v, ans])

print(ans)

Fixed submission:
def main():
    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:]))
 
 
main()

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

h, n = map(int, input().split())

INF = 10 ** 20

dp = collections.defaultdict(lambda : INF)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))



que = [0]
cc = [0]
while que:
    next_que = set()
    for i in que:
        now_dam = i
        for a, b in magic:
            dam = now_dam + a
            dp[dam] = min([dp[dam], dp[now_dam] + b])
            if dam < h:
                next_que.add(dam)
    que = list(next_que)

ans = INF

for k, v in dp.items():
    if k >= h:
        ans = min([v, ans])

print(ans)

Fixed submission:
def main():
    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:]))
 
 
main()