def solve():

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

    attack = []

    mp = []

    for i in range(N):

        a,b = list(map(int,input().split()))

        attack.append(a)

        mp.append(b)

    

    max_attack = max(attack)

    dp = [[float('inf')] * (H+max_attack) for _ in range(N+1)]



    for i in range(N+1):

        dp[i][0] = 0

    

    for i in range(N):

        for j in range(H+max_attack):

            if j - attack[i] >= 0:

                dp[i+1][j] = min(dp[i+1][j], dp[i][j-attack[i]]+mp[i], dp[i+1][j-attack[i]]+mp[i])

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

    

    ans = float('inf')

    for i in range(N+1):

        for j in range(H,H+max_attack):

            ans = min(ans, dp[i][j])

    

    print(ans)



if __name__ == '__main__':

    solve()
def solve():

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

    ap = []

    mp = []



    for _ in range(N):

        a,b = list(map(int,input().split()))

        ap.append(a)

        mp.append(b)

    

    ap_max = max(ap)

    

    dp = [[float('inf')] * (H+ap_max+1) for _ in range(N+1)]

    for i in range(N+1):

        dp[i][0] = 0

    

    for i in range(N):

        for sum_h in range(H+ap_max+1):

            dp[i+1][sum_h] = min(dp[i][sum_h-ap[i]] + mp[i], dp[i][sum_h])

            dp[i+1][sum_h] = min(dp[i+1][sum_h-ap[i]] + mp[i], dp[i][sum_h])

    

    ans = float('inf')

    for sum_h in range(H, H+ap_max+1):

        ans = min(ans,dp[N][sum_h])



    print(ans)



if __name__ == '__main__':

    solve()
def solve():
    H, N = list(map(int, input().split()))
    attack = []
    mp = []
    for i in range(N):
        a, b = list(map(int, input().split()))
        attack.append(a)
        mp.append(b)
    max_attack = max(attack)
    dp = [[float("inf")] * (H + max_attack) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 0
    for i in range(N):
        for j in range(H + max_attack):
            if j - attack[i] >= 0:
                dp[i + 1][j] = min(
                    dp[i + 1][j],
                    dp[i][j - attack[i]] + mp[i],
                    dp[i + 1][j - attack[i]] + mp[i],
                )
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
    ans = float("inf")
    for i in range(N + 1):
        for j in range(H, H + max_attack):
            ans = min(ans, dp[i][j])
    print(ans)


if __name__ == "__main__":
    solve()

def solve():
    H, N = list(map(int, input().split()))
    ap = []
    mp = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        ap.append(a)
        mp.append(b)
    ap_max = max(ap)
    dp = [[float("inf")] * (H + ap_max + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 0
    for i in range(N):
        for sum_h in range(H + ap_max + 1):
            dp[i + 1][sum_h] = min(dp[i][sum_h - ap[i]] + mp[i], dp[i][sum_h])
            dp[i + 1][sum_h] = min(dp[i + 1][sum_h - ap[i]] + mp[i], dp[i][sum_h])
    ans = float("inf")
    for sum_h in range(H, H + ap_max + 1):
        ans = min(ans, dp[N][sum_h])
    print(ans)


if __name__ == "__main__":
    solve()

-    attack = [] +    ap = [] -    for i in range(N): +    for _ in range(N): -        attack.append(a) +        ap.append(a) -    max_attack = max(attack) -    dp = [[float("inf")] * (H + max_attack) for _ in range(N + 1)] +    ap_max = max(ap) +    dp = [[float("inf")] * (H + ap_max + 1) for _ in range(N + 1)] -        for j in range(H + max_attack): -            if j - attack[i] >= 0: -                dp[i + 1][j] = min( -                    dp[i + 1][j], -                    dp[i][j - attack[i]] + mp[i], -                    dp[i + 1][j - attack[i]] + mp[i], -                ) -            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]) +        for sum_h in range(H + ap_max + 1): +            dp[i + 1][sum_h] = min(dp[i][sum_h - ap[i]] + mp[i], dp[i][sum_h]) +            dp[i + 1][sum_h] = min(dp[i + 1][sum_h - ap[i]] + mp[i], dp[i][sum_h]) -    for i in range(N + 1): -        for j in range(H, H + max_attack): -            ans = min(ans, dp[i][j]) +    for sum_h in range(H, H + ap_max + 1): +        ans = min(ans, dp[N][sum_h])