// Slower C++ solution:
/*Function Template*/

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

typedef pair<ll,ll> pint;

const int MAX = 510000;

const int MOD = 1000000007;

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

#define Rep(i, n) for(ll i = 1; i < (n); i++)

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll fac[MAX], finv[MAX], inv[MAX];





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;

}

// テーブルを作る前処理

void COMinit() {

    fac[0] = fac[1] = 1;

    finv[0] = finv[1] = 1;

    inv[1] = 1;

    for (ll i = 2; i < MAX; i++){

        fac[i] = fac[i - 1] * i % MOD;

        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

        finv[i] = finv[i - 1] * inv[i] % MOD;

    }



}

ll Len(ll n) {

  ll s=0;

  while(n!=0) s++, n/=10;

  return s;

}





ll Sint(ll n) {

  ll m=0,s=0,a=n;

  while(a!=0) s++, a/=10;

  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;

  return m;

}





ll Svec(vector<ll> v){

  ll n=0;

  for(ll i=0;i<v.size();i++) n+=v[i];

  return n;

}





ll GCD(ll a,ll b) {

  return b ? GCD(b,a%b) : a;

}





ll LCM(ll a,ll b){

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

}





ll Factorial(ll n){

  ll m=1;

  while(n>=1) m*=n,n--;

  return m;

}



void runlength(string s,vector<pair<char,ll>> &p){

  ll x=1;

  if(s.size()==1){

    p.push_back(pair<char,ll>(s[0],1));

  }

  for(ll i=0;i<s.size()-1;i++){

    if(s[i]==s[i+1]){

      x++;

      if(i==s.size()-2){

        p.push_back(pair<char,ll>(s[i],x));

      }

    }else{

      p.push_back(pair<char,ll>(s[i],x));

      x=1;

      if(i==s.size()-2){

        p.push_back(pair<char,ll>(s[s.size()-1],x));

      }

    }

  }

}









ll COM(ll n,ll k){

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

}



const int MAX_N=100010;

vector<bool> sieve_of_eratosthenes(){

  vector<bool> isPrime(MAX_N+1,true);

  for(int i=2;i<=MAX_N;i++){

    if(isPrime[i]){

      for(int j=2*i;j<=MAX_N;j+=i){

        isPrime[j]=false;

      }

    }

  }

  return isPrime;

}



vector<pint> prime_factorize(ll n){

  vector<pint> ans;

  for(ll p=2;p<=sqrt(n);p++){

    if(n%p!=0) continue;

    ll cnt=0;

    while(n%p==0){

      n/=p;

      cnt++;

    }

    ans.push_back(make_pair(p,cnt));

  }

  if(n!=1) ans.push_back(make_pair(n,1));

  return ans;

}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/

int main() {

  IOS;

  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,1e10));

  dp[0][0]=0;

  rep(i,n){

    rep(j,h+1){

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

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

    }

  }

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

  

  

  

}

// Faster C++ solution for the same problem (measured speedup: 2.2689257161641807x):
/*Function Template*/

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

typedef pair<ll,ll> pint;

const int MAX = 510000;

const int MOD = 1000000007;

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

#define Rep(i, n) for(ll i = 1; i < (n); i++)

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll fac[MAX], finv[MAX], inv[MAX];





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;

}

// テーブルを作る前処理

void COMinit() {

    fac[0] = fac[1] = 1;

    finv[0] = finv[1] = 1;

    inv[1] = 1;

    for (ll i = 2; i < MAX; i++){

        fac[i] = fac[i - 1] * i % MOD;

        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

        finv[i] = finv[i - 1] * inv[i] % MOD;

    }



}

ll Len(ll n) {

  ll s=0;

  while(n!=0) s++, n/=10;

  return s;

}





ll Sint(ll n) {

  ll m=0,s=0,a=n;

  while(a!=0) s++, a/=10;

  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;

  return m;

}





ll Svec(vector<ll> v){

  ll n=0;

  for(ll i=0;i<v.size();i++) n+=v[i];

  return n;

}





ll GCD(ll a,ll b) {

  return b ? GCD(b,a%b) : a;

}





ll LCM(ll a,ll b){

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

}





ll Factorial(ll n){

  ll m=1;

  while(n>=1) m*=n,n--;

  return m;

}



void runlength(string s,vector<pair<char,ll>> &p){

  ll x=1;

  if(s.size()==1){

    p.push_back(pair<char,ll>(s[0],1));

  }

  for(ll i=0;i<s.size()-1;i++){

    if(s[i]==s[i+1]){

      x++;

      if(i==s.size()-2){

        p.push_back(pair<char,ll>(s[i],x));

      }

    }else{

      p.push_back(pair<char,ll>(s[i],x));

      x=1;

      if(i==s.size()-2){

        p.push_back(pair<char,ll>(s[s.size()-1],x));

      }

    }

  }

}









ll COM(ll n,ll k){

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

}



const int MAX_N=100010;

vector<bool> sieve_of_eratosthenes(){

  vector<bool> isPrime(MAX_N+1,true);

  for(int i=2;i<=MAX_N;i++){

    if(isPrime[i]){

      for(int j=2*i;j<=MAX_N;j+=i){

        isPrime[j]=false;

      }

    }

  }

  return isPrime;

}



vector<pint> prime_factorize(ll n){

  vector<pint> ans;

  for(ll p=2;p<=sqrt(n);p++){

    if(n%p!=0) continue;

    ll cnt=0;

    while(n%p==0){

      n/=p;

      cnt++;

    }

    ans.push_back(make_pair(p,cnt));

  }

  if(n!=1) ans.push_back(make_pair(n,1));

  return ans;

}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/

int main() {

  IOS;

  ll h,n;

  cin>>h>>n;

  vector<ll> w(n),v(n);

  rep(i,n) cin>>w[i]>>v[i];

  ll dp[h+1];

  rep(i,h+1) dp[i]=1e11;

  dp[0]=0;

  rep(i,n) rep(j,h+1) chmin(dp[min(j+w[i],h)],dp[j]+v[i]);

  cout<<dp[h]<<endl; 

}