#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

int main() {
  int h,n;
  cin>>h>>n;
  vector<int> dp(h+1,100000005);
  dp[0] = 0;
  rep(i,n){
    int a,b;
    cin>>a>>b;
    rep(j,h+1){
      int nj = min(h,j+a);
      dp[nj] = min(dp[j]+b,dp[nj]);
    }
    
  }
  cout << dp[h] << endl;
}
