#include <bits/stdc++.h>
using namespace std;

// #include <boost/algorithm/string/join.hpp>
// using boost::algorithm::join;
//
#include "boost/multi_array.hpp"
// boost::multi_array<int, 3> dp;
// dp.resize(boost::extents[10][9][8]);
//
// #include <boost/multiprecision/cpp_dec_float.hpp>  // quite slowly
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision; // mp::log10
// using bigint = boost::multiprecision::cpp_int;
// using rational = mp::cpp_rational;  // double d = static_cast<double>(r);

typedef long long ll;
typedef unsigned long long ull;
//typedef long double ld;

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

//constexpr ll MOD = 1e9+7;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/4;
constexpr int INF=inf<int>;
constexpr ll LINF=inf<ll>;

#define Sort(x) sort(begin(x),end(x))
#define Reverse(x) reverse(begin(x),end(x))
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ull<<(n))
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,(v).size())

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
#define endl "\n"
  }
} before_main_function;

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseImplicitTreap {
  // T0上の演算、単位元
  virtual T0 f0(T0, T0) = 0;
  const T0 u0;
  // T1上の演算、単位元
  virtual T1 f1(T1, T1) = 0;
  const T1 u1;
  // T0に対するT1の作用
  virtual T0 g(T0, T1) = 0;
  // 多数のt1(T1)に対するf1の合成
  virtual T1 p(T1, int) = 0;

  class xorshift {
    uint64_t x;

    public:
    xorshift() {
      mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
      x = rnd();
      for (int i = 0; i < 100; i++) {
        random();
      }
    }

    uint64_t random() {
      x = x ^ (x << 7);
      return x = x ^ (x >> 9);
    }
  } rnd;

  struct Node {
    T0 value, acc;
    T1 lazy;
    int priority, cnt;
    bool rev;
    Node *l, *r;

    Node(T0 value_, int priority_, T0 u0_, T1 u1_)
      : value(value_), acc(u0_), lazy(u1_), priority(priority_), cnt(1), rev(false), l(nullptr), r(nullptr) {}
  } *root = nullptr;

  using Tree = Node *;

  int cnt(Tree t) { return t ? t->cnt : 0; }

  T0 acc(Tree t) { return t ? t->acc : u0; }

  void update_cnt(Tree t) {
    if (t) {
      t->cnt = 1 + cnt(t->l) + cnt(t->r);
    }
  }

  void update_acc(Tree t) {
    if (t) {
      t->acc = f0(acc(t->l), f0(t->value, acc(t->r)));
    }
  }

  void pushup(Tree t) { update_cnt(t), update_acc(t); }

  void pushdown(Tree t) {
    if (t && t->rev) {
      t->rev = false;
      swap(t->l, t->r);
      if (t->l) t->l->rev ^= 1;
      if (t->r) t->r->rev ^= 1;
    }
    if (t && t->lazy != u1) {
      if (t->l) {
        t->l->lazy = f1(t->l->lazy, t->lazy);
        t->l->acc = g(t->l->acc, p(t->lazy, cnt(t->l)));
      }
      if (t->r) {
        t->r->lazy = f1(t->r->lazy, t->lazy);
        t->r->acc = g(t->r->acc, p(t->lazy, cnt(t->r)));
      }
      t->value = g(t->value, p(t->lazy, 1));
      t->lazy = u1;
    }
    pushup(t);
  }

  void split(Tree t, int key, Tree &l, Tree &r) {
    if (!t) {
      l = r = nullptr;
      return;
    }
    pushdown(t);
    int implicit_key = cnt(t->l) + 1;
    if (key < implicit_key) {
      split(t->l, key, l, t->l), r = t;
    } else {
      split(t->r, key - implicit_key, t->r, r), l = t;
    }
    pushup(t);
  }

  void insert(Tree &t, int key, Tree item) {
    Tree t1, t2;
    split(t, key, t1, t2);
    merge(t1, t1, item);
    merge(t, t1, t2);
  }

  void merge(Tree &t, Tree l, Tree r) {
    pushdown(l);
    pushdown(r);
    if (!l || !r) {
      t = l ? l : r;
    } else if (l->priority > r->priority) {
      merge(l->r, l->r, r), t = l;
    } else {
      merge(r->l, l, r->l), t = r;
    }
    pushup(t);
  }

  void erase(Tree &t, int key) {
    Tree t1, t2, t3;
    split(t, key + 1, t1, t2);
    split(t1, key, t1, t3);
    merge(t, t1, t2);
  }

  void update(Tree t, int l, int r, T1 x) {
    if (l >= r) return;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    t2->lazy = f1(t2->lazy, x);
    t2->acc = g(t2->acc, p(x, cnt(t2)));
    merge(t2, t2, t3);
    merge(t, t1, t2);
  }

  T0 query(Tree t, int l, int r) {
    if (l == r) return u0;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    T0 ret = t2->acc;
    merge(t2, t2, t3);
    merge(t, t1, t2);
    return ret;
  }

  // [l, r)の中で左から何番目か
  int find(Tree t, T0 x, int offset, bool left = true) {
    if (f0(t->acc, x) == x) {
      return -1;
    } else {
      if (left) {
        if (t->l && f0(t->l->acc, x) != x) {
          return find(t->l, x, offset, left);
        } else {
          return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left);
        }
      } else {
        if (t->r && f0(t->r->acc, x) != x) {
          return find(t->r, x, offset + cnt(t->l) + 1, left);
        } else {
          return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left);
        }
      }
    }
  }

  void reverse(Tree t, int l, int r) {
    if (l > r) return;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    t2->rev ^= 1;
    merge(t2, t2, t3);
    merge(t, t1, t2);
  }

  // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様
  void rotate(Tree t, int l, int m, int r) {
    reverse(t, l, r);
    reverse(t, l, l + r - m);
    reverse(t, l + r - m, r);
  }

  void dump(Tree t) {
    if (!t) return;
    pushdown(t);
    dump(t->l);
    cout << t->value << " ";
    dump(t->r);
  }

  public:
  BaseImplicitTreap(T0 u0_, T1 u1_) : u0(u0_), u1(u1_) {}

  void set_by_vector(const vector<T0> &a) {
    for (int i = 0; i < int(a.size()); i++) {
      insert(i, a[i]);
    }
  }

  int size() { return cnt(root); }

  void insert(int pos, T0 x) { insert(root, pos, new Node(x, rnd.random(), u0, u1)); }

  void update(int l, int r, T1 x) { update(root, l, r, x); }

  T0 query(int l, int r) { return query(root, l, r); }

  // 二分探索。[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のもの。存在しない場合は-1
  // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す
  int binary_search(int l, int r, T0 x, bool left = true) {
    if (l >= r) return -1;
    Tree t1, t2, t3;
    split(root, l, t1, t2);
    split(t2, r - l, t2, t3);
    int ret = find(t2, x, l, left);
    merge(t2, t2, t3);
    merge(root, t1, t2);
    return ret;
  }

  void erase(int pos) { erase(root, pos); }

  void reverse(int l, int r) { reverse(root, l, r); }

  void rotate(int l, int m, int r) { rotate(root, l, m, r); }

  void dump() {
    dump(root);
    cout << endl;
  }

  T0 operator[](int pos) { return query(pos, pos + 1); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseImplicitTreap<T0, T1> {
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
  T0 f0(T0 x, T0 y) override { return min(x, y); }
  T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
  T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
  T1 p(T1 x, int len) override { return x; }
};

// ========== end of template ==========
constexpr int A_MAX=1e4;

int main(int argc, char** argv) {
  int H, N;
  cin >> H >> N;
  vi A(N), B(N);
  REP(i, N) {
    cin >> A[i] >> B[i];
  }

  vi dp(H+A_MAX+1, INF);
  dp[0] = 0;

  REP(i, H) {
    REP(j, N) {
      chmin(dp[i+A[j]], dp[i] + B[j]);
    }
  }

  int ret = INF;
  REP(i, H, dp.size()) {
    chmin(ret, dp[i]);
  }

  cout << ret << endl;

  return 0;
}

/* vim: set expandtab shiftwidth=2 softtabstop=2 : */


Measured memory_bytes: 384