Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        if dp[i] == maxsize:
            continue
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = map(int, input().split())
    for j in range(H):
        t1 = j + A
        if t1 > H:
            t1 = H
        t2 = dp[j] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print(dp[H])


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(1, H + max_A + 1):
        for a, b in AB:
            t1 = i - a
            if t1 < 0:
                continue
            t2 = dp[t1]
            if t2 == inf:
                continue
            if t2 + b < dp[i]:
                dp[i] = t2 + b
    print(min(dp[H:]))
main()


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

max_A = max(a for a, _ in AB)
inf = float('inf')
dp = [inf] * (H + max_A + 1)
dp[0] = 0
for i in range(1, H + max_A + 1):
    for a, b in AB:
        t1 = i - a
        if t1 < 0:
            continue
        t2 = dp[t1]
        if t2 == inf:
            continue
        if t2 + b < dp[i]:
            dp[i] = t2 + b
print(min(dp[H:]))


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [100000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for j in range(N):
        a, b = AB[j]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [100000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for j in range(N):
        a, b = AB[j]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))

Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()

Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [1000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 1000000:
        continue
    for j in range(N):
        a, b = AB[k]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))


Fixed submission:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()