Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print(min(dp[H:]))


if __name__ == "__main__":
    main()


Fixed submission:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H and dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
            elif i + a >= H and dp[i] + b < dp[H]:
                dp[H] = dp[i] + b
    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    
    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if i not in dp:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


if __name__ == "__main__":
    main()