// Slower C++ solution:
#include <bits/stdc++.h>

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

#define rrep(i,n) for(int i = 1; i <= (n); ++i)

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

#define srep(i,s,t) for (int i = s; i < t; ++i)

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

#define rrng(x) (x).rbegin(),(x).rend()

#define limit(x,l,r) max(l,min(x,r))

#define lims(x,l,r) (x = max(l,min(x,r)))

#define isin(x,l,r) ((l) <= (x) && (x) < (r))

#define show(x) cout << #x << " = " << (x) << endl

#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl

#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')

#define showv2(v) rep(j,v.size()) showv(v[j])

#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')

#define showt2(t,r,c) rep(j,r) showt(t[j],c)

#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);

#define printv(v) rep(i,v.size()) printf("%d\n", v[i])

#define printt(t,n) rep(i,n) printf("%d\n", t[i])

#define incl(v,x) find(rng(v),x)!=v.end()

#define fi first

#define se second

#define pb push_back

#define eb emplace_back

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

#define pcnt __builtin_popcountll

#define bn(x) ((1<<x)-1)

#define dup(x,y) (((x)+(y)-1)/(y))

#define newline puts("")

#define uni(x) x.erase(unique(rng(x)),x.end())

#define SP << " " <<

using namespace std;

using ll = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using vll = vector<ll>;

using pii = pair<int, int>;

using tiii = tuple<int, int, int>;

typedef vector<pii> vp;

typedef vector<tiii> vt;

const int mod = 1000000007;

const double EPS = 1e-9;

const int INF = (1<<30)-1;

const ll INFLL = (1LL<<62)-1;

#define dame { puts("No"); return 0;}

#define yn {puts("Yes");}else{puts("No");}

inline int in() { int x; scanf("%d",&x); return x;}

//cout << fixed << setprecision(10);

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; }



int dp[100050];



int main () {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i,n) {

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

  }



  rep(i,100050) dp[i] = INF;

  dp[0] = 0;

  rep(i,50000) {

    rep(j,n) {

      if (dp[i] == INF) continue;

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

    }

  }



  int ans = INF;

  for (int i = h; i <= h+10000; ++i) {

    chmin(ans, dp[i]);

  }

  cout << ans << endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.422554138136578x):
#include <bits/stdc++.h>

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

#define rrep(i,n) for(int i = 1; i <= (n); ++i)

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

#define srep(i,s,t) for (int i = s; i < t; ++i)

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

#define rrng(x) (x).rbegin(),(x).rend()

#define limit(x,l,r) max(l,min(x,r))

#define lims(x,l,r) (x = max(l,min(x,r)))

#define isin(x,l,r) ((l) <= (x) && (x) < (r))

#define show(x) cout << #x << " = " << (x) << endl

#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl

#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')

#define showv2(v) rep(j,v.size()) showv(v[j])

#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')

#define showt2(t,r,c) rep(j,r) showt(t[j],c)

#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);

#define printv(v) rep(i,v.size()) printf("%d\n", v[i])

#define printt(t,n) rep(i,n) printf("%d\n", t[i])

#define incl(v,x) find(rng(v),x)!=v.end()

#define fi first

#define se second

#define pb push_back

#define eb emplace_back

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

#define pcnt __builtin_popcountll

#define bn(x) ((1<<x)-1)

#define dup(x,y) (((x)+(y)-1)/(y))

#define newline puts("")

#define uni(x) x.erase(unique(rng(x)),x.end())

#define SP << " " <<

using namespace std;

using ll = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using vll = vector<ll>;

using pii = pair<int, int>;

using tiii = tuple<int, int, int>;

typedef vector<pii> vp;

typedef vector<tiii> vt;

const int mod = 1000000007;

const double EPS = 1e-9;

const int INF = (1<<30)-1;

const ll INFLL = (1LL<<62)-1;

#define dame { puts("No"); return 0;}

#define yn {puts("Yes");}else{puts("No");}

inline int in() { int x; scanf("%d",&x); return x;}

//cout << fixed << setprecision(10);

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; }



int dp[100001];



int main () {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i,n) {

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

  }



  rep(i,100000) dp[i] = INF;

  dp[0] = 0;

  rep(i,h+1) {

    rep(j,n) {

      if (dp[i] == INF) continue;

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

    }

  }



  int ans = INF;

  for (int i = h; i < h+*max_element(rng(a)); ++i) {

    chmin(ans, dp[i]);

  }

  cout << ans << endl;

  return 0;

}