# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/4
# @File : E - Crested Ibis vs Monster (完全背包改版）.py

# https://atcoder.jp/contests/abc153/tasks/abc153_e

# 根据完全背包的代码改。

def dp_WQ_2Beibao(a,b,h,n):
    dp = [[100000000]*(h+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 0
    for i in range(1,n+1):
        for j in range(1,h+1):
            if(j < a[i]):#就比如现在的技能i 可以造成伤害为3， 现在的j值为 2  你一样可以动用这技能造成怪物2点伤害（然后还多了一个点），所以这里就不能直接等于dp[i-1][j]，也要用上这个b[i]（自身输出）来作比较看谁小。
                dp[i][j]=min(dp[i-1][j],b[i])
            else:
                dp[i][j]=min(dp[i-1][j],dp[i][j-a[i]]+b[i])
    return dp[-1][-1]
if __name__ == "__main__":
    h,n = map(int ,input().split())
    a = [0]
    b = [0]
    for _ in range(n):
        rate = [int(i) for i in input().split()]
        a.append(rate[0])
        b.append(rate[1])
    print(dp_WQ_2Beibao(a,b,h,n))
"""
区别：
完全背包：求最大价值。不能大于背包容量。
打怪兽：求最小输出。可以大于怪物能量。

所以初始化的时候有不同，其他基本相同。

"""