#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vout(v) VOUT(v,z);
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL);
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}


void solve_old(long long H, long long N, std::vector<long long> A, std::vector<long long> B){
    vector<double> v(N);
    ll ma=0, mai=0;
    for (ll i = 0; i < N; i++) {
        v[i]=(1.0*A[i])/B[i];
        if(ma<v[i]) {
            ma=v[i];
            mai=i;
        }
    }
    debg(mai);
    ll secma=0,secmai=-1;
    for (ll i = 0; i < N; i++) {
        if(B[i]<=(B[mai]/2)){
            if(secma<v[i]){
                secma=v[i];
                secmai=i;
            }
        }
    }
    debg(secmai);
    // ll ret=((H+A[mai]-1)/A[mai])*B[mai];
    // cout << ret << "\n";
    ll ret=0;
    if(secmai!=-1){
        ll secnum=B[mai]/B[secmai];
        H-=(secnum*A[secmai]);
        ret+=(secnum*B[secmai]);
    }
    ret+=((H+A[mai]-1)/A[mai])*B[mai];
    // ret+=(H/A[mai])*B[mai];
    ll Hres=H-(H/A[mai])*A[mai];
    debg(Hres);
    cout << ret << "\n";
}

void solve(long long H, long long N, std::vector<long long> A, std::vector<long long> B){
    vector<ll> dp(2e4+5,INF);
    dp[0]=0;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < dp.size(); j++) {
            if(j+A[i]<dp.size())
                dp[j+A[i]]=min(dp[j+A[i]],dp[j]+B[i]);
        }
    }
    ll ret=INF;
    for (ll i = H; i < dp.size(); i++) {
        chmin(ret,dp[i]);
    }
    cout << ret << "\n";
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(H, N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 384