// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#define ll long long

#define rep(i,n) for(int i=0;i<(n);i++)

#define repp(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

using namespace std;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

typedef pair<int,int> P;

typedef pair<ll,ll> Pll;

//小数点以下　cout << fixed << setprecision(10) << num << endl;

//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA

//long*long<0で判定するな

//開区間と閉区間

//アルファベットが何番目かは x=s[i]-'a'

//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ

//切り上げ：(a+(b-1))/b

//32bit以上は 1ull<<j]

// map 初期値0 for(auto itr=mp.begin();itr!=mp.end();++itr) itr->fi itr->se で全探索

// for(auto u:mp) u.fi u.se も可能

//n個のgcd,lcmは一つずつみて更新していく

//大きな数を扱うときは素因数分解した形で持っておく

// (l/a[i]) = l*powmod(a[i],MOD-2)%MOD;

const int INF = 100100100;

int main(){

    int h,n; cin>>h>>n;

    int a[n],b[n];

    rep(i,n) cin >> a[i] >> b[i];

    ll dp[n+1][30020];

    memset(dp,INF,sizeof(dp));

    dp[0][0]=0;

    rep(i,n){

        rep(j,30020){

            if(j-a[i]>=0){

               dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i]);

            }

            else dp[i+1][j]=dp[i][j];

        }

    }

    ll ans=INF;

    rep(j,30020) if(j>=h) ans=min(ans,dp[n][j]);

    rep(i,n+1){

        //rep(j,h+1) cout << dp[i][j] << " ";

        //cout << endl;

    }

    cout  << ans << endl;

}




// Faster C++ solution for the same problem (measured speedup: 2.6481720036707728x):
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#include <functional>

#include <cctype>

#include <locale>

#define ll long long

#define rep(i,n) for(int i=0;i<(n);i++)

#define rrep(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

#define ALL(a) (a).begin(),(a).end()

using namespace std;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

typedef pair<int,int> P;

typedef pair<long long,long long> Pll;

#define fout(num) cout << fixed << setprecision(20) << (num) << endl

//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ

//vector<vector<ll>> dp(n,vector<ll>(n))

//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));

//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));



signed main(){

    const int INF = 1e9;

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    int h,n; cin >> h >> n;

    vector<int> dp(h+1,INF);

    dp[0]=0;

    rep(i,n){

        int a,b;

        cin >> a >> b;

        rep(j,h+1){

            int x=min(h,j+a);

            chmin(dp[x],dp[j]+b);

        }

    }

    cout << dp[h] << endl;

}