// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <utility>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <map>

#include <math.h>

#include <string.h>

#include <iomanip>

#include <numeric>



using namespace std;



using ll = long long;

using pll = pair<ll, ll>;

using vl = vector<ll>;

using vll = vector<vl>;

using vpll = vector<pll>;



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

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

#define pb push_back

#define eb emplace_back



struct Edge{

    int to;

    int weight;

    Edge(int t, int w) : to(t), weight(w){ }

};



using Graph = vector<vector<Edge>>;

using graph = vector<vector<int>>;



template <class T>

inline bool chmin(T &a, T b){

    if (a > b){

        a = b;

        return true;

    }

    return false;

}



template <class T>

inline bool chmax(T &a, T b){

    if (a < b){

        a = b;

        return true;

    }

    return false;

}



template <class T>

T gcd(T a, T b){

    if( b==0 ) return a;

    else return gcd(b, a%b);

}



template <class T>

T lcm(T a, T b){

    return (a*b)/gcd(a,b);

}



ll INF = 1e9+7;



template<class T>

void dcomb(T n,T m, string s){

    if(n==0) cout << s << endl;

    else {

        for(T i=0; i<m; ++i){

            dcomb(n-1,m,s+to_string(i));

        }

    }

}



int main(){

    ll h,n;

    cin >> h >> n;

    vector<ll> a(n), b(n);

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

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

    dp[0][0] = 0;

    rep(i,n){

        rep(j,h+1){

            chmin(dp[i+1][j],dp[i][j]);

            chmin(dp[i+1][min(h,j+a[i])],dp[i+1][j]+b[i]);

        }

    }

    cout << dp[n][h] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <utility>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <map>

#include <math.h>

#include <string.h>

#include <iomanip>

#include <numeric>

#include <cstdlib>

#include <cstdint>

#include <cmath>



using namespace std;



using ll = long long;

using pll = pair<ll, ll>;

using vl = vector<ll>;

using vll = vector<vl>;

using vpll = vector<pll>;



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

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

#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)

#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)

#define pb push_back

#define eb emplace_back



struct Edge{

    int to;

    int weight;

    Edge(int t, int w) : to(t), weight(w){ }

};



using Graph = vector<vector<Edge>>;

using graph = vector<vector<int>>;



template <class T>

inline bool chmin(T &a, T b){

    if (a > b){

        a = b;

        return true;

    }

    return false;

}



template <class T>

inline bool chmax(T &a, T b){

    if (a < b){

        a = b;

        return true;

    }

    return false;

}



template <class T>

T gcd(T a, T b){

    if( b==0 ) return a;

    else return gcd(b, a%b);

}



template <class T>

T lcm(T a, T b){

    return (a*b)/gcd(a,b);

}



int INF = 1e9+7;



vector<int> dx = {-1,0,1,0};

vector<int> dy = {0,-1,0,1};



int main(){

    int h,n;

    cin >> h >> n;

    vector<int> a(n),b(n);

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

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

    dp[0] = 0;

    rep(i,n){

        rep(j,h){

            chmin(dp[min(h,j+a[i])],dp[j]+b[i]);

        }

    }

    cout << dp[h] << endl;

}

// Fastest known solution for this problem: