// Original C++ solution (slower):
// template version 1.15

using namespace std;

#include <bits/stdc++.h>



// varibable settings

#define int long long

const int INF=1e18;



// define basic macro {{{

#define _overload3(_1,_2,_3,name,...) name

#define _rep(i,n) repi(i,0,n)

#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define _rrep(i,n) rrepi(i,0,n)

#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)

#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)

#define each(i,a) for (auto&& i : a)

#define all(x) (x).begin(),(x).end()

#define sz(x) ((int)(x).size())

#define pb(a) push_back(a)

#define mp(a, b) make_pair(a, b)

#define mt(a, b, c) make_tuple(a, b, c)

#define divceil(a,b) ((a)+(b)-1)/(b)

#define is_in(x, a, b) ((a)<=(x) && (x)<(b))

#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())

#define ub upper_bound

#define lb lower_bound

#define posl(A, x) (lower_bound(all(A), x)-A.begin())

#define posu(A, x) (upper_bound(all(A),x)-A.begin())

template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }

template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }



typedef long long ll;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef long double ld;

typedef pair<int,int> pii;

typedef tuple<int,int,int> iii;



template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;

struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;



#if defined(PCM) || defined(LOCAL)

  #include "lib/dump.hpp"

#else

  #define dump(...) 42

  #define dump_1d(...) 42

  #define dump_2d(...) 42

  #define cerrendl 42

#endif

//}}}



signed main() {

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



  vi a(n), b(n);

  vector<pii> ab;

  rep(i, n){

    cin>>a[i]>>b[i];

    ab.pb(mp(a[i], b[i]));

  }

  // sort(all(ab));

  dump(ab);



  const int H = 10000;

  vvi dp(n+1, vi(h+H+1, INF));

  dp[0][0] = 0;



  rep(i, 1, n+1){

    rep(d, 0, h+H+1){

      chmin(dp[i][d], dp[i-1][d]);

      if (d-a[i-1]>=0) chmin(dp[i][d], dp[i][d-a[i-1]]+b[i-1]);

    }

  }



  int ans = INF;

  rep(d, h, h+H+1){

    chmin(ans, dp[n][d]);

  }

  cout << ans << endl;



  return 0;

}


// Optimized solution to the same problem (faster):
// template version 1.15

using namespace std;

#include <bits/stdc++.h>



// varibable settings

#define int long long

const int INF=1e18;



// define basic macro {{{

#define _overload3(_1,_2,_3,name,...) name

#define _rep(i,n) repi(i,0,n)

#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define _rrep(i,n) rrepi(i,0,n)

#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)

#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)

#define each(i,a) for (auto&& i : a)

#define all(x) (x).begin(),(x).end()

#define sz(x) ((int)(x).size())

#define pb(a) push_back(a)

#define mp(a, b) make_pair(a, b)

#define mt(a, b, c) make_tuple(a, b, c)

#define divceil(a,b) ((a)+(b)-1)/(b)

#define is_in(x, a, b) ((a)<=(x) && (x)<(b))

#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())

#define ub upper_bound

#define lb lower_bound

#define posl(A, x) (lower_bound(all(A), x)-A.begin())

#define posu(A, x) (upper_bound(all(A),x)-A.begin())

template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }

template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }



typedef long long ll;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef long double ld;

typedef pair<int,int> pii;

typedef tuple<int,int,int> iii;



template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;

struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;



#if defined(PCM) || defined(LOCAL)

  #include "lib/dump.hpp"

#else

  #define dump(...) 42

  #define dump_1d(...) 42

  #define dump_2d(...) 42

  #define cerrendl 42

#endif

//}}}



signed main(){

  int n,h;

  cin>>h>>n;

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

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



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

  dp[0]=0;

  rep(i,n) rep(j,h+1){

  // rep(i,n) rrep(j,h+1){ // 01 napsack

    chmin(dp[min(j+v[i], h)], dp[j]+w[i]);  // jから配る

  }

  cout<<dp[h]<<endl;

  return 0;

}


// Fastest known solution for this problem: