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

int main() {
  int maxHP, N;
  cin >> maxHP >> N;
  vector<int> MP(maxHP + 1, 1e9);
  MP.at(0) = 0;
  for (int i = 0; i < N; i++) {
    int dmg, mpc;
    cin >> dmg >> mpc;
    for (int nowHP = 0; nowHP < maxHP; nowHP++) {
      MP.at(min(nowHP + dmg, maxHP)) = min(MP.at(min(nowHP + dmg, maxHP)), MP.at(nowHP) + mpc);
    }
  }
  cout << MP.at(maxHP) << "\n";
}