import sys

sys.setrecursionlimit(1000000) # 再帰上限を増やす



def main():

    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！

    H, N = list(map(int, input().rstrip().split()))

    magic_list = []

    for _ in range(N):

        A, B = list(map(int, input().rstrip().split()))

        magic_list.append((A, B))



    dp = [[100000000] * (H+1) for _ in range(N+1)]

    # dp[i][hp] = i番目までの魔法を使って、hpのダメージを与えるための最小魔力

    dp[0][0] = 0

    for i, magic in enumerate(magic_list):

        damage, mp = magic

        for hp in range(H+1):

            # i番目までの魔法を使って、与えられるダメージの最小魔力の結果をコピー

            dp[i+1][hp] = min(dp[i+1][hp], dp[i][hp])

            # 魔法を使用する場合、i+1番目までの魔法を使って、HP+damageのダメージの魔力最小値であれば更新

            dp[i+1][min(H, hp+damage)] = min(dp[i+1][min(H, hp+damage)], dp[i+1][hp] + mp)

    print((dp[N][H]))



if __name__ == '__main__':

    main()
import sys

sys.setrecursionlimit(1000000) # 再帰上限を増やす



def main():

    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！

    H, N = list(map(int, input().rstrip().split()))

    magic_list = []

    for _ in range(N):

        A, B = list(map(int, input().rstrip().split()))

        magic_list.append((A, B))



    # dp[hp] = hpのダメージを与えるための最小魔力

    dp = [100000000] * (H+1)

    # 0のダメージを与えるのに必要な最小魔力は0

    dp[0] = 0

    # 各魔法に関して探索

    for i, magic in enumerate(magic_list):

        damage, mp = magic

        # 各ダメージを与えるのに必要な最小魔力を更新する

        # (与えられないダメージ数の場合は最大値で初期化してあるので、最大値のまま更新されない)

        for hp in range(H+1):

            # 魔法を使用する場合のダメージについて、必要魔力が現在計算されている中での最小値であれば更新

            dp[min(H, hp+damage)] = min(dp[min(H, hp+damage)], dp[hp] + mp)

    print((dp[H]))



if __name__ == '__main__':

    main()
import sys

sys.setrecursionlimit(1000000)  # 再帰上限を増やす


def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    H, N = list(map(int, input().rstrip().split()))
    magic_list = []
    for _ in range(N):
        A, B = list(map(int, input().rstrip().split()))
        magic_list.append((A, B))
    dp = [[100000000] * (H + 1) for _ in range(N + 1)]
    # dp[i][hp] = i番目までの魔法を使って、hpのダメージを与えるための最小魔力
    dp[0][0] = 0
    for i, magic in enumerate(magic_list):
        damage, mp = magic
        for hp in range(H + 1):
            # i番目までの魔法を使って、与えられるダメージの最小魔力の結果をコピー
            dp[i + 1][hp] = min(dp[i + 1][hp], dp[i][hp])
            # 魔法を使用する場合、i+1番目までの魔法を使って、HP+damageのダメージの魔力最小値であれば更新
            dp[i + 1][min(H, hp + damage)] = min(
                dp[i + 1][min(H, hp + damage)], dp[i + 1][hp] + mp
            )
    print((dp[N][H]))


if __name__ == "__main__":
    main()

import sys

sys.setrecursionlimit(1000000)  # 再帰上限を増やす


def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    H, N = list(map(int, input().rstrip().split()))
    magic_list = []
    for _ in range(N):
        A, B = list(map(int, input().rstrip().split()))
        magic_list.append((A, B))
    # dp[hp] = hpのダメージを与えるための最小魔力
    dp = [100000000] * (H + 1)
    # 0のダメージを与えるのに必要な最小魔力は0
    dp[0] = 0
    # 各魔法に関して探索
    for i, magic in enumerate(magic_list):
        damage, mp = magic
        # 各ダメージを与えるのに必要な最小魔力を更新する
        # (与えられないダメージ数の場合は最大値で初期化してあるので、最大値のまま更新されない)
        for hp in range(H + 1):
            # 魔法を使用する場合のダメージについて、必要魔力が現在計算されている中での最小値であれば更新
            dp[min(H, hp + damage)] = min(dp[min(H, hp + damage)], dp[hp] + mp)
    print((dp[H]))


if __name__ == "__main__":
    main()

-    dp = [[100000000] * (H + 1) for _ in range(N + 1)] -    # dp[i][hp] = i番目までの魔法を使って、hpのダメージを与えるための最小魔力 -    dp[0][0] = 0 +    # dp[hp] = hpのダメージを与えるための最小魔力 +    dp = [100000000] * (H + 1) +    # 0のダメージを与えるのに必要な最小魔力は0 +    dp[0] = 0 +    # 各魔法に関して探索 +        # 各ダメージを与えるのに必要な最小魔力を更新する +        # (与えられないダメージ数の場合は最大値で初期化してあるので、最大値のまま更新されない) -            # i番目までの魔法を使って、与えられるダメージの最小魔力の結果をコピー -            dp[i + 1][hp] = min(dp[i + 1][hp], dp[i][hp]) -            # 魔法を使用する場合、i+1番目までの魔法を使って、HP+damageのダメージの魔力最小値であれば更新 -            dp[i + 1][min(H, hp + damage)] = min( -                dp[i + 1][min(H, hp + damage)], dp[i + 1][hp] + mp -            ) -    print((dp[N][H])) +            # 魔法を使用する場合のダメージについて、必要魔力が現在計算されている中での最小値であれば更新 +            dp[min(H, hp + damage)] = min(dp[min(H, hp + damage)], dp[hp] + mp) +    print((dp[H]))