Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率が高い順にソート
# 効率が同じなら、小規模な順
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

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

sys.setrecursionlimit(10 ** 8)

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


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        return min(b + dp(h - a) for a, b in AB)


print(dp(H))


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

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

dp = [float("inf")] * (H + AB[-1][0])
dp[0] = 0
for i in range(1, len(dp)):
    for a, b in AB:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            break

ans = min(dp[H:])
print(ans)



Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

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

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
dp = [float("inf")] * (H + AB[-1][0])
dp[0] = 0
for i in range(1, len(dp)):
    for a, b in AB:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            break

ans = min(dp[H:])
print(ans)



Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

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

AB.append((0, 1))

dp = [float("inf")] * (10 ** 4 * 2 + 1)
dp[0] = 0
for i in range(1, len(dp)):
    for a, b in AB:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)

ans = min(dp[H:])
print(ans)


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

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


dp = [0] * (10 ** 8 + 1)
for i in range(1, len(dp)):
    for a, b in AB:
        if i - b >= 0:
            dp[i] = max(dp[i], dp[i - b] + a)
    if dp[i] >= H:
        break

ans = bisect_left(dp[: i + 1], H)
print(ans)


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))