#include <bits/stdc++.h>
using namespace std;
int main () {
  int H, N;
  cin >> H >> N;
  vector<long> HP(H + 1, 100000000000000);
  HP.at(0) = 0;
  long A, B;
  for(int i = 0; i < N; i++){
    cin >> A >> B;
    for(int i = 0; i < H; i++){
      if(i + A > H)HP.at(H) = min(HP.at(H), HP.at(i) + B);
      else HP.at(i + A) = min(HP.at(i + A), HP.at(i) + B);
    }
  }
  cout << HP.at(H) << endl;
  return 0;
}
