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

const int INF=1001001001;

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