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

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])


Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

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

H, N = list(map(int, input().split()))
AB = []
for n in range(N):
    AB.append(list(map(int, input().split())))

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])


Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
"""問題文
トキはモンスターと戦っています。
モンスターの体力は  H  です。
トキは  N  種類の魔法が使え、 i  番目の魔法を使うと、モンスターの体力を  A i  減らすことができますが、トキの魔力を  B i  消耗します。
同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を  0  以下にすればトキの勝ちです。  トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。
"""
from functools import lru_cache
import sys


# @lru_cache(maxsize=1000)
# def attack(h, mp):
#     """
#     毎回Nパターン選択肢がある
#     最小値を返す
#     """
#     min_mp = 999999
#     for a, b in sorted_ab_list:
#         new_h = h - a
#         new_mp = mp + b
#
#         if new_mp >= min_mp:
#             # 既に最小値超えてたら中断
#             continue
#
#         if new_h > 0:
#             min_mp = min(min_mp, attack(new_h, new_mp))
#         else:
#             min_mp = min(min_mp, new_mp)
#
#     # 最小値をとる
#     return min_mp


def use_dp():
    max_a = max([ab[0] for ab in AB])
    dp = [sys.maxsize for i in range(H+1)]
    dp[0] = 0

    # 各ダメージ段階の最小値を求める
    for i in range(H):
        if dp[i] == sys.maxsize:
            continue
        # 各魔法を使って最小値なら更新
        for j in range(N):
            a = min(i + AB[j][0], H)
            b = dp[i] + AB[j][1]
            if dp[a] > b:
                dp[a] = b

    min_mp = dp[H]

    # H < i < H+max(Ai)の範囲で最小値を求める
    # min_mp = sys.maxsize
    # for i in range(H, H+max_a):
    #     min_mp = min(dp[i], min_mp)

    print(min_mp)


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB = []
    for n in range(N):
        AB.append(list(map(int, input().split())))

    use_dp()

    # sorted_ab_list = sorted(AB_list, key=lambda x: x[0]/x[1], reverse=True)
    #
    # print(attack2(H))


Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
"""問題文
トキはモンスターと戦っています。
モンスターの体力は  H  です。
トキは  N  種類の魔法が使え、 i  番目の魔法を使うと、モンスターの体力を  A i  減らすことができますが、トキの魔力を  B i  消耗します。
同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を  0  以下にすればトキの勝ちです。  トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。
"""
from functools import lru_cache
import sys


# @lru_cache(maxsize=1000)
# def attack(h, mp):
#     """
#     毎回Nパターン選択肢がある
#     最小値を返す
#     """
#     min_mp = 999999
#     for a, b in sorted_ab_list:
#         new_h = h - a
#         new_mp = mp + b
#
#         if new_mp >= min_mp:
#             # 既に最小値超えてたら中断
#             continue
#
#         if new_h > 0:
#             min_mp = min(min_mp, attack(new_h, new_mp))
#         else:
#             min_mp = min(min_mp, new_mp)
#
#     # 最小値をとる
#     return min_mp
#
#
# def attack2(h):
#     t_mp = 0
#     t_a = sorted_ab_list[0][0]
#     t_b = sorted_ab_list[0][1]
#     while h > 0:
#         h = h-a
#         t_mp += b
#
#     # やり直しが必要
#     if h < 0:
#         over_h = -h
#         mp = t_mp - t_b
#         # filter_list = [i for i in sorted_ab_list if i[0] > 1]
#     return mp


def use_dp():
    max_a = max([ab[0] for ab in AB])
    dp = [sys.maxsize for i in range(H+max_a)]
    dp[0] = 0

    # 各ダメージ段階の最小値を求める
    for i in range(H):
        if dp[i] == sys.maxsize:
            continue
        # 各魔法を使って最小値なら更新
        for j in range(N):
            a = i + AB[j][0]
            b = dp[i] + AB[j][1]
            if dp[a] > b:
                dp[a] = b

    # H < i < H+max(Ai)の範囲で最小値を求める
    min_mp = sys.maxsize
    for i in range(H, H+max_a):
        min_mp = min(dp[i], min_mp)

    print(min_mp)


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB = []
    for n in range(N):
        AB.append(list(map(int, input().split())))

    use_dp()

    # sorted_ab_list = sorted(AB_list, key=lambda x: x[0]/x[1], reverse=True)
    #
    # print(attack2(H))


Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

Buggy python submission (verdict: Runtime Error):
def use_dp():
    max_a = max([ab[0] for ab in AB])
    dp = [sys.maxsize for i in range(H+max_a)]
    dp[0] = 0

    # 各ダメージ段階の最小値を求める
    for i in range(H):
        if dp[i] == sys.maxsize:
            continue
        # 各魔法を使って最小値なら更新
        for j in range(N):
            a = i + AB[j][0]
            b = dp[i] + AB[j][1]
            if dp[a] > b:
                dp[a] = b

    # H < i < H+max(Ai)の範囲で最小値を求める
    min_mp = sys.maxsize
    for i in range(H, H+max_a):
        min_mp = min(dp[i], min_mp)

    print(min_mp)


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB = []
    for n in range(N):
        AB.append(list(map(int, input().split())))

    use_dp()

Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

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


@lru_cache(maxsize=1000)
def attack(h, mp):
    """
    毎回Nパターン選択肢がある
    最小値を返す
    """
    min_mp = 999999
    for a, b in sorted_ab_list:
        new_h = h - a
        new_mp = mp + b

        if new_mp >= min_mp:
            # 既に最小値超えてたら中断
            continue

        if new_h > 0:
            min_mp = min(min_mp, attack(new_h, new_mp))
        else:
            min_mp = min(min_mp, new_mp)

    # 最小値をとる
    return min_mp


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB_list = []
    for n in range(N):
        a, b = list(map(int, input().split()))
        AB_list.append([a, b])

    sorted_ab_list = sorted(AB_list, key=lambda x: x[0]/x[1], reverse=True)

    print(attack(H, 0))

Fixed submission:
import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])