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

input = sys.stdin.readline

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

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))



Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = []
dp[0] = 0
for i in range(h+max_cost+1):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))



Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
magics = sorted([list(map(int, input().split())) for _ in range(n)])
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)

dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))



Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)

dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))



Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))

Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    h, n = map(int, input().split())

    magics = []
    max_cost = 0
    for _ in range(n):
        at, cost = map(int, input().split())
        max_cost = max(max_cost, cost)
        magics.append((at, cost))

    dp = [float('inf')] * (h+max_cost)
    dp[0] = 0
    for i in range(len(dp)):
        for at, cost in magics:
            if at <= i:
                dp[i] = min(dp[i], dp[i-at] + cost)
    print(min(dp[h:]))

main()


Fixed submission:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))