#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
 
/*** Template Begins ***/
 
typedef unsigned long long    ll;
typedef pair<ll,ll>  pll;
typedef pair<ll, pair<int, int> > plll;
typedef vector<long long>  vll;
typedef vector<pll>  vp;
typedef long double ld;
#define pb           push_back
#define INF          INT_MAX/10
#define F            first
#define S            second
#define mp           make_pair
// #define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
// #define h 998244353
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p)
{
  ll res = 1;
  x = x % p;
  while (y > 0)
  { 
    if (y & 1) 
      res = (res*x) % p;
    y = y>>1;
    x = (x*x) % p;
  } 
  return res; 
} 
const int MAXN = 2e5+5;

// Debug //
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
// #define trace6(a, n,i;b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// Constants //
 
/*** Template Ends ***/


void solve()
{
  ll n,h;
  cin>>h>>n;
  vector<ll> w(n+1),p(n+1);
  ll i,j;
  ll limit = 2*h;
  for(i=1;i<=n;i++)
  {
    cin>>w[i]>>p[i];
    limit = max(limit,2*w[i]);
  }
  ll dp[n+1][limit+1];
  for(i=0;i<n+1;i++)
    for(j=0;j<limit+1;j++)
      dp[i][j]=hell;
  trace(limit);  
  for(i=1;i<=n;i++)
    dp[i][0]=0;
  for(i=0;i<=limit;i++)
    dp[0][i]=hell;
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=limit;j++)
    {
      if(w[i]<=j)
        dp[i][j] = min(dp[i-1][j],dp[i][j-w[i]]+p[i]);
      else
        dp[i][j] = dp[i-1][j];
    }
    for(j=limit-1;j>0;j--)
      dp[i][j]=min(dp[i][j+1],dp[i][j]);
  }
//   for(i=0;i<=limit;i++)
//     cout<<i<<"\t";
//   cout<<endl;
//   for(i=1;i<=n;i++)
//   {
//     for(j=0;j<=limit;j++)
//       if(dp[i][j]!=hell)
//         cout<<dp[i][j]<<"\t";
//       else
//         cout<<-1<<" ";
//     cout<<endl;  
// }
  // ll ans = hell;
  // for(i=h;i<=limit;i++)
    // ans = min(ans,dp[n][]);
  cout<<dp[n][h];
}
int main()
{ 
  // ios;
  // fxreopen("inputt.txt", "w", stdout);
  ll t;
  // cin >> t;
  t=1;
  while(t--)
    solve();
  return 0;
}

Measured memory_bytes: 156800