#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

class Cooperative {
public:
  int q;
  int r;
  Cooperative(int q, int r) : q(q), r(r) {}
  ~Cooperative() {}
  friend bool operator<(const Cooperative &a, const Cooperative &b) { return !(a.q < b.q); }
  friend std::ostream &operator<<(std::ostream &s, Cooperative &c) { return s << "(" << c.q << "," << c.r << ")"; }
};

void read_data(int &m, int &n, std::vector<Cooperative>&c) {
#define ALPHA 1
#if 0
  std::cin >> m;
  std::cin >> n;

  c.reserve(n * ALPHA);
  for (int i = 0; i < n; i++) {
    int q, r;
    std::cin >> q, std::cin >> r;
    c.push_back(Cooperative(q, r));
#endif
  scanf("%d", &m);
  scanf("%d", &n);
  c.reserve(n * ALPHA);
  for (int i = 0; i < n; i++) {
    int q, r;
    scanf("%d %d\n", &q, &r);
    c.push_back(Cooperative(q, r));
  }  
}

void dump(int m, int n, std::vector<Cooperative>&c) {
  std::cout << "m = " << m << std::endl;
  std::cout << "n = " << n << std::endl;
  for (size_t i = 0; i < c.size(); i++)
    std::cout << c[i] << ", ";
  std::cout << std::endl;
}

/*-----------------------------------------------------------------*/
class Phase {
public:
  int mTotal;
  int rTotal;
  int last_pos;
  std::vector<int> combination;
  Phase(int n, int idx, int q, int r) : mTotal(q), rTotal(r) {
    combination.reserve(n);
    last_pos = 0;
    combination[last_pos] = idx;
  }

  Phase(int n, const Phase *org) {
    combination.reserve(n);
    this->mTotal = org->mTotal;
    this->rTotal = org->rTotal;
    this->last_pos = org->last_pos;
    for (int i = 0; i <= this->last_pos; i++)
      this->combination[i] = this->combination[i];
  }

  void addCooperative(int idx, int q, int r) {
    this->mTotal += q;
    this->rTotal += r;
    this->combination[++last_pos] = idx;
  }
};

void searchPreparation(std::queue<Phase *>&q, std::vector<Cooperative>&c) {
  for (int i = 0; i < c.size(); i++)
    q.push(new Phase(c.size(), i, c[i].q, c[i].r));
}

int searchLoop(std::queue<Phase *>&q, std::vector<Cooperative>&c, int m) {
  int min_r = 0;
  int t;
  Phase *nowchecking;
  for (int i = 0; i < c.size(); i++) min_r += c[i].r;
  while (!q.empty()) {
    nowchecking = q.front();
    q.pop();
    if (nowchecking->mTotal >= m) {
      if ((t = nowchecking->rTotal) < min_r) {
        min_r = t;
      }
      delete nowchecking;
    } else { /* making child-node and add those to queue and deleted himself */
      for (int i = nowchecking->combination[nowchecking->last_pos] + 1; i < c.size(); i++) {
        if (nowchecking->rTotal + c[i].r >= min_r)
          continue;
        Phase *Child = new Phase(c.size(), nowchecking);
        Child->addCooperative(i, c[i].q, c[i].r);
        q.push(Child);
      }
      delete nowchecking;
    }
  } /* !q.empty()? */
  return min_r;
}

int searchBestSolution(int m, std::vector<Cooperative>&c) {
  std::queue<Phase *> q;
  searchPreparation(/*ref*/q, /*ref*/c);
  return searchLoop(/*ref*/q, /*ref*/c, m);
}

/*-----------------------------------------------------------------*/
#include <cassert>
int addCombinationAll(std::vector<int> &c) {
  int n;
  for (n = c.size() - 1; n >= 0; --n) {
    if (!c[n]) {
      c[n] = 1;
      return 0;
    }
    c[n] = 0;
  }
  assert(n < 0);
  return 1;
}

int reference(int m, std::vector<Cooperative>&c) {
  std::vector<int> combinationAll(c.size(), 0);
  int min_r;
  for (int i = 0; i < c.size(); i++) min_r += c[i].r;

  while (!addCombinationAll(combinationAll)) {
    int rTotal = 0;
    int mTotal = 0;
    for (int i = 0; i < c.size(); i++) {
      if (combinationAll[i]) {
        rTotal += c[i].r;
        mTotal += c[i].q;
      }
    }
    if (mTotal >= m && rTotal < min_r) 
        min_r = rTotal;
  }
  return min_r;
}
/*-----------------------------------------------------------------*/
int main() {
  int m, n;
  std::vector<Cooperative> c;

  read_data(/*ref*/m, /*ref*/n, /*ref*/c);
  sort(c.begin(), c.end());
//  dump(m, n, /*ref*/c);
//  std::cout << reference(m, /*ref*/c) << std::endl;
  std::cout << searchBestSolution(m, /*ref*/c) << std::endl;
  return 0;
}
/* end */