#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// How to use 「map」
/*
  - 宣言
    map<{key_type}, {value_type}> salary;
  - 要素の挿入
    salary["Alice"] = 1000;
  - 要素の取得 O(logn)
    salary.at("Alice");
  - 要素の削除
    salary.erase("Alice");
  - キー検索
    salary.find("Alice"); -> true
    salary.find("Bob");   -> false
  - イテレーション
    for(auto& [key, value] : salary) {...}
 */
// -------------------------------------


// How to use 「lower_bound」, 「upper_bound」
/*
  vector<int> a = {1, 2, 3, 4, 5};
  auto iter1 = lower_bound(all(a), 3);  <- 第二引数「以上」の最小イテレータが返る
  auto iter2 = upper_bound(all(a), 3);  <- 第二引数「より大きい」最小のイテレータが返る
 */
// -------------------------------------


// How to use 「struct sort」
/*
  struct Person {
    string name;
    int age;

    Person(string _name, int _age) {
      name = _name;
      age = _age;
    }

    bool operator<(const Person &another) const {
      return age < another.age;
    }
  };

  vector<Person> people;
  people.pb(Person("Alice", 20));
  people.pb(Person("Bob", 19));
  people.pb(Person("John", 40));
  people.pb(Person("Chris", 30));
  sort(all(people));
 */
 // -------------------------------------

// -------------------------------------------------------------------------------------

ll dp[1001][10001];

int main() {
  rep(i, 1001) {
    rep(j, 10001) {
      if (j == 0) {
        dp[i][j] = 0;
      } else {
        dp[i][j] = INF<ll>;
      }
    }
  }

  ll h, n;
  cin >> h >> n;

  vector< pair<ll, ll> > magics;
  rep(i, n) {
    ll a, b;
    cin >> a >> b;
    magics.pb(mp(a, b));
  }

  pair<ll, ll> firstMagic = magics[0];
  rep1(j, h+1) {
    if (j <= firstMagic.first) {
      dp[0][j] = firstMagic.second;
    } else {
      dp[0][j] = dp[0][j - firstMagic.first] + firstMagic.second;
    }
  }

  rep1(i, n) {
    pair<ll, ll> magic = magics[i];
    rep1(j, h+1) {
      if (j <= magic.first) {
        dp[i][j] = min(dp[i-1][j], magic.second);
      } else {
        ll pattern1 = dp[i-1][j];
        ll pattern2 = dp[i][j-magic.first] + magic.second;
        ll pattern3 = dp[i-1][j-magic.first] + magic.second;
        dp[i][j] = min(pattern1, pattern2, pattern3);
      }
    }
  }

  // rep(i, n) {
  //   rep(j, h+1) {
  //     cout << dp[i][j] << ",";
  //   }
  //   cout << endl;
  // }

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

  return 0;
}

Measured memory_bytes: 78464