stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int main() {



 int H, N;

 cin >> H >> N;



 vector<int> A(N);

 vector<int> B(N);

 for (int i = 0; i < N; i++) {

   cin >> A[i] >> B[i];

 }



 // i 番目までの魔法からダメージの総和が j になるように選んだときの魔法消費量の総和の最小値

 vector<vector<int>> dp(N + 1, vector<int>(H + 1, 100000000));



 dp[0][0] = 0;



 for (int i = 0; i < N; i++) {

   for (int j = 0; j <= H; j++) {

     if (j <= A[i]) {

       dp[i+1][j] = min(dp[i][j], B[i]);

     } else {

       dp[i+1][j] = min(dp[i][j], dp[i+1][j - A[i]] + B[i]);

     }

   }

 }



 cout << dp[N][H] << endl;



}

// Faster C++ solution for the same problem (measured speedup: 1.521389886202722x):
// 公式Youtubeより

// INFが大きすぎるとdp[j]+Bが負になってしまうので注意が必要

#include <bits/stdc++.h>

using namespace std;

#define rep(i,N) for(int i=0;i<int(N);++i)

using ll = long long;

const int MOD = 1e9 + 7;

const int INF = 1001001001;

// const ll INF = 1000000000000000000LL;



int main(){

    int h, n;

    cin >> h >> n;

    vector<int> dp(h+1, INF);

    dp[0] = 0;

    rep(i,n) {

        int a, b;

        cin >> a >> b;

        rep(j,h) {

        int nj = min(j+a,h);

        dp[nj] = min(dp[nj], dp[j]+b);

        }

    }

    cout << dp[h] << endl;

    return 0;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e8;

  vector<vector<int>> dp(n + 1, vector<int>(mx, INF));

  dp[0][0] = 0;

  rep(i, n) {

    int a, b;

    cin >> a >> b;

    rep(j, mx) {

      if (j - a >= 0) {

        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b);

      } else {

        dp[i + 1][j] = dp[i][j];

      }

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[n][i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7765825259085866x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dpOld(mx, INF), dpNew(mx, INF);

  dpOld[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    rep(i, mx) {

      if (i - a >= 0) {

        dpNew[i] = min(dpOld[i], dpNew[i - a] + b);

      } else {

        dpNew[i] = dpOld[i];

      }

      dpOld[i] = dpNew[i];

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dpNew[i]);

  }

  cout << ans;

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e8;

  vector<vector<int>> dp(n + 1, vector<int>(mx, INF));

  dp[0][0] = 0;

  rep(i, n) {

    int a, b;

    cin >> a >> b;

    rep(j, mx) {

      if (j - a >= 0) {

        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b);

      } else {

        dp[i + 1][j] = dp[i][j];

      }

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[n][i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.1504907163956712x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dp(mx, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = a; i < mx; i++) {

      dp[i] = min(dp[i], dp[i - a] + b);

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[i]);

  }

  cout << ans;

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dpOld(mx, INF), dpNew(mx, INF);

  dpOld[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    rep(i, mx) {

      if (i - a >= 0) {

        dpNew[i] = min(dpOld[i], dpNew[i - a] + b);

      } else {

        dpNew[i] = dpOld[i];

      }

      dpOld[i] = dpNew[i];

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dpNew[i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.210464858814177x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dp(mx, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = a; i < mx; i++) {

      dp[i] = min(dp[i], dp[i - a] + b);

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[i]);

  }

  cout << ans;

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e8;

  vector<vector<int>> dp(n + 1, vector<int>(mx, INF));

  dp[0][0] = 0;

  rep(i, n) {

    int a, b;

    cin >> a >> b;

    rep(j, mx) {

      if (j - a >= 0) {

        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a] + b);

      } else {

        dp[i + 1][j] = dp[i][j];

      }

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[n][i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.283521812974625x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

  vector<int> dp(h + 1, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = 0; i <= h; i++) {

      int j = min(i + a, h);

      dp[j] = min(dp[j], dp[i] + b);

    }

  }

  cout << dp[h];

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dpOld(mx, INF), dpNew(mx, INF);

  dpOld[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    rep(i, mx) {

      if (i - a >= 0) {

        dpNew[i] = min(dpOld[i], dpNew[i - a] + b);

      } else {

        dpNew[i] = dpOld[i];

      }

      dpOld[i] = dpNew[i];

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dpNew[i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.285345194874512x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

  vector<int> dp(h + 1, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = 0; i <= h; i++) {

      int j = min(i + a, h);

      dp[j] = min(dp[j], dp[i] + b);

    }

  }

  cout << dp[h];

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dp(mx, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = a; i < mx; i++) {

      dp[i] = min(dp[i], dp[i - a] + b);

    }

  }

  int ans = INF;

  for (int i = h; i < mx; i++) {

    ans = min(ans, dp[i]);

  }

  cout << ans;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0618608095188249x):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

  vector<int> dp(h + 1, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = 0; i <= h; i++) {

      int j = min(i + a, h);

      dp[j] = min(dp[j], dp[i] + b);

    }

  }

  cout << dp[h];

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using vi = vector<int>;

using vl = vector<ll>;

using vvi = vector<vi>;

using vvl = vector<vl>;

#define ote(x) cout<<(x)<<endl

#define all(x) (x).begin(),(x).end()

#define rp(i,s,e) for(int i=(s);i<(e);++i)

#define rpz(i,e) rp(i,0,(e))

#define irp(i,s,e) for(int i=(s);i>(e);--i)

#define irpz(i,s) irp(i,(s),-1)

template<class T> T in(){T x;cin>>x;return x;}

// long long a = in<long long>();

template<class T> vector<T> inarr(int s,int e, T init=0){

	vector<T> v;T x;

	rp(i,0,s)v.push_back(init);

	rp(i,s,e){x=in<T>();v.push_back(x);}

	return v;

}

// vi P = inarr<int>(1,N+1,INT_MAX);

// vi P = inarr<int>(0,N);



// #define NMAX 1000000000

int H,N;

string S, T;

using PLL = pair<ll,ll>;

using VP = vector<PLL>;

VP AB;



ll solve(){

	ll ans=0;



	// rp(i,0,AB.size()){

	// 	cout<<i<<" ";

	// 	cout<<AB[i].first<<" "<<AB[i].second<<"\n";

	// }



	ll INF = LLONG_MAX>>2;

	vvl dp(N+1, vl(H+1, INF));

	dp[0][0] = 0;

	rp(i,1,N+1){

		ll mp,hp;tie(hp,mp)=AB[i-1];

		rp(j,0,H+1){

			if(j==0) dp[i][j] = 0;

			if(j-hp>=0) dp[i][j] = min(dp[i-1][j], dp[i][j-hp] + mp);

			else dp[i][j] = min(dp[i-1][j], mp);



		}

	}



	ans = dp[N][H];

	return ans;

}



int main(){

	cin>>H;

	cin>>N;

	rp(i,0,N){

		int a,b;

		cin>>a>>b;

		AB.emplace_back(a,b);

	}

	cout<< solve() <<endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.3753198186556925x):
// E - Crested Ibis vs Monster

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#define rp(i,s,e) for(int i=(s);i<(e);++i)

vi A,B;

int H,N;



int solve(){

	int INF = INT_MAX>>2;

	vvi dp(N+1, vi(H+1, INF));

	dp[0][0] = 0;

	rp(i,1,N+1){

		int hp = A[i-1], mp = B[i-1];

		rp(j,0,H+1){

			if(j == 0) dp[i][j] = 0;

			else if(j-hp >= 0) dp[i][j] = min(dp[i-1][j], dp[i][j-hp] + mp);

			else dp[i][j] = min(dp[i-1][j], mp);

		}

	}

	return dp[N][H];

}



int main(){

	cin>>H>>N;

	rp(i,0,N){

		int a,b; cin>>a>>b;

		A.push_back(a);

		B.push_back(b);

	}

	cout<< solve() <<endl;

}
// Slower C++ solution:
// ABC158-E 

#include <bits/stdc++.h>

#define endl "\n"

#define rep(i,n) for(int i=0;i<int(n);i++)

#define SZ(x) ((int)(x).size())

#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)

{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

namespace you {

    std::string to_string(char val) {

        return std::string(1, val);

        // return std::string{val};

        // you::to_string(char)

    }

}



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(12);



    int h,n;

    cin>>h>>n;

    vector<int> a(n+1);

    vector<int> b(n+1);



    int max_=0;

    rep(i,n){

        cin>>a[i+1]>>b[i+1];

        if(a[i+1]>max_) max_=a[i+1];

    }

    vector<vector<int>> dp(n+1,vector<int>(h+max_,pow(10,9)));



    for(int i=1;i<=n;i++){

        for(int j=1;j<=h+max_-1;j++){

            if(a[i]<=j){

                if(dp[i][j-a[i]]==pow(10,9)){

                    if(j==a[i]) dp[i][j]=min(b[i],dp[i-1][j]);

                    else dp[i][j]=min(dp[i][j],dp[i-1][j]);

                }else{

                    dp[i][j]=min(dp[i-1][j],dp[i][j-a[i]]+b[i]);

                }

            }else dp[i][j]=min(dp[i-1][j],dp[i][j]);

            //cout<<dp[i][j]<<endl;

        }

    }

    int ans=pow(10,9);

    for(int i=1;i<=n;i++){

        for(int j=h;j<h+max_;j++){

            if(dp[i][j]<ans) ans=dp[i][j];

        }

    }

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.622704718159351x):
// ABC153-E

#include <bits/stdc++.h>

#define endl "\n"

#define rep(i,n) for(int i=0;i<int(n);i++)

#define e_b emplace_back

#define sz(x) ((int)(x).size())

#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> ipair;

typedef pair<ll,ll> lpair;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る

{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る

void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る





int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(12);



    ll h,n;

    cin>>h>>n;

    vector<ll> a(n);

    vector<ll> b(n);

    rep(i,n){

        cin>>a[i]>>b[i];

    }

    ll inf=pow(10,18);

    vector<ll> dp(h+100,inf);

    dp[0]=0;

    rep(i,n){ //使う魔法

        rep(j,h){ //スタート地点

            ll next=min(h,j+a[i]);

            if(dp[j]!=inf) dp[next]=min(dp[next],dp[j]+b[i]);

        }

    }

    cout<<dp[h]<<endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <cassert>

typedef long long int ll;

using namespace std;



// @@ !! LIM()



int main(int argc, char *argv[]) {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout << setprecision(20);



  ll H, N; cin >> H >> N;

  vector<ll> A(N), B(N);

  for (ll i = 0; i < N; i++) cin >> A.at(i) >> B.at(i);

  vector<vector<ll>> dp(N+1, vector<ll>(H+1, 1e10));

  dp.at(0).at(0) = 0;

  for (ll i = 0; i < N; i++) {

    ll a = A.at(i);

    dp.at(i+1).at(0) = 0;

    for (ll j = 1; j <= H; j++) {

      ll base = j-a >= 0 ? dp.at(i+1).at(j-a) : 0;

      dp.at(i+1).at(j) = min(dp.at(i).at(j), base + B.at(i));

    }

  }

  cout << dp.at(N).at(H) << endl;



  return 0;

}




// Faster C++ solution for the same problem (measured speedup: 2.2313314045926074x):
#include <bits/stdc++.h>

#include <cassert>

typedef long long int ll;

using namespace std;



// @@ !! LIM(f:updMaxMin)

// --> f:updMaxMin

// ---- inserted function updMaxMin from util.cc

template<typename T>

bool updMax(T& tmax, const T& x) {

  if (x > tmax) { tmax = x; return true;  }

  else          {           return false; }

}

template<typename T>

bool updMin(T& tmin, const T& x) {

  if (x < tmin) { tmin = x; return true;  }

  else          {           return false; }

}

// ---- end updMaxMin

// @@ !! LIM  -- end mark --



int main(/* int argc, char *argv[] */) {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout << setprecision(20);



  ll H, N; cin >> H >> N;

  vector<ll> A(N), B(N);

  for (ll i = 0; i < N; i++) cin >> A[i] >> B[i];



  ll big = 1e12;

  vector cur(H + 1, big);

  cur[0] = 0;

  for (ll i = 0; i < N; i++) {

    for (ll h = 0; h < H; h++) {

      ll g = min(h + A[i], H);

      updMin(cur[g], cur[h] + B[i]);

    }

  }

  cout << cur[H] << endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

typedef long long ll;

using namespace std;

template <class T>

inline bool chmax(T& a, T b) {

  if (a < b) {

    a = b;

    return 1;

  }

  return 0;

}

template <class T>

inline bool chmin(T& a, T b) {

  if (a > b) {

    a = b;

    return 1;

  }

  return 0;

}

const ll INF = 1ll << 60;



int main() {

  int h, n;

  cin >> h >> n;

  vector<int> a(n), b(n);

  for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];



  vector<vector<long long>> dp(n + 1, vector<long long>(h + 1, INF));

  dp[0][0] = 0;

  for (int i = 0; i < n; ++i) {

    for (int j = 0; j <= h; ++j) {

      chmin(dp[i + 1][j], dp[i][j]);

      chmin(dp[i + 1][min(j + a[i], h)], dp[i + 1][j] + b[i]);

    }

  }

  cout << dp[n][h] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.1935049655262064x):
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)



typedef long long ll;

using namespace std;

const ll INF = 1ll << 60;



int main() {

  int h, n, a, b;

  cin >> h >> n;

  vector<ll> dp(h + 1, INF);

  dp[0] = 0;



  rep(i, n) {

    cin >> a >> b;

    rep(j, h) dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b);

  }



  cout << dp[h] << endl;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



const ll INF = LONG_LONG_MAX / 2;



vector<vector<ll>> dp;

vector<ll> A;

vector<ll> B;



ll solve(int i, int j, const int H, const int N) {

    if (dp[i][j] >= 0) {

        return dp[i][j];

    }



    ll ans = solve(i - 1, j, H, N);

    chmin(ans, solve(i, max(0LL, j - A[i]), H, N) + B[i]);

    dp[i][j] = ans;

    return ans;

}



int main(void) {

    int H, N;

    cin >> H >> N;



    A.resize(N + 1);

    B.resize(N + 1);

    for (int i = 0; i < N; i++) {

        int a, b;

        cin >> a >> b;

        A[i + 1] = a;

        B[i + 1] = b;

    }



    dp.resize(N + 1, vector<ll>(H + 1, -1));

    for (int i = 0; i <= H; i++) {

        dp[0][i] = INF;

    }

    for (int i = 0; i <= N; i++) {

        dp[i][0] = 0;

    }



    solve(N, H, H, N);



    cout << dp[N][H] << endl;

    

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.5861352128957276x):
#include <algorithm>

#include <cassert>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



const int INF = INT_MAX / 2;



// {damage, mp}

vector<pair<int, int>> magics;



vector<vector<int>> dp;



int main(void) {

    int H, N;

    cin >> H >> N;



    magics.resize(N + 1);

    for (int i = 0; i < N; i++) {

        int a, b;

        cin >> a >> b;

        magics[i + 1] = {a, b};

    }



    dp.resize(N + 1, vector<int>(H + 1, INF));

    dp[0][0] = 0;



    for (int i = 0; i < N; i++) {

        auto magic = magics[i + 1];

        for (int j = 0; j <= H; j++) {

            chmin(dp[i + 1][j], dp[i][j]);

            if (j <= magic.first) {

                chmin(dp[i + 1][j], dp[i][0] + magic.second);

            } else {

                chmin(dp[i + 1][j], dp[i][j - magic.first] + magic.second);

                chmin(dp[i + 1][j], dp[i + 1][j - magic.first] + magic.second);

            }

        }

    }



    cout << dp[N][H] << endl;



    // for (int i = 0; i <= N; i++) {

    //     for (int j = 0; j <= H; j++) {

    //         cout << dp[i][j] << " ";

    //     }

    //     cout << endl;

    // }



    return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



const ll INF = LONG_LONG_MAX / 2;



vector<vector<ll>> dp;

vector<ll> A;

vector<ll> B;



void solve(const int H, const int N) {

    for (int i = 1; i <= N; i++) {

        for (int j = 1; j <= H; j++) {

            dp[i][j] = dp[i - 1][j];

            chmin(dp[i][j], dp[i][max(0LL, j - A[i])] + B[i]);

        }

    }

}



int main(void) {

    int H, N;

    cin >> H >> N;



    A.resize(N + 1);

    B.resize(N + 1);

    for (int i = 0; i < N; i++) {

        int a, b;

        cin >> a >> b;

        A[i + 1] = a;

        B[i + 1] = b;

    }



    dp.resize(N + 1, vector<ll>(H + 1, -1));

    for (int i = 0; i <= H; i++) {

        dp[0][i] = INF;

    }

    for (int i = 0; i <= N; i++) {

        dp[i][0] = 0;

    }



    solve(H, N);



    cout << dp[N][H] << endl;

    

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3462291134131275x):
#include <algorithm>

#include <cassert>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



const int INF = INT_MAX / 2;



// {damage, mp}

vector<pair<int, int>> magics;



vector<vector<int>> dp;



int main(void) {

    int H, N;

    cin >> H >> N;



    magics.resize(N + 1);

    for (int i = 0; i < N; i++) {

        int a, b;

        cin >> a >> b;

        magics[i + 1] = {a, b};

    }



    dp.resize(N + 1, vector<int>(H + 1, INF));

    dp[0][0] = 0;



    for (int i = 0; i < N; i++) {

        auto magic = magics[i + 1];

        for (int j = 0; j <= H; j++) {

            chmin(dp[i + 1][j], dp[i][j]);

            if (j <= magic.first) {

                chmin(dp[i + 1][j], dp[i][0] + magic.second);

            } else {

                chmin(dp[i + 1][j], dp[i][j - magic.first] + magic.second);

                chmin(dp[i + 1][j], dp[i + 1][j - magic.first] + magic.second);

            }

        }

    }



    cout << dp[N][H] << endl;



    // for (int i = 0; i <= N; i++) {

    //     for (int j = 0; j <= H; j++) {

    //         cout << dp[i][j] << " ";

    //     }

    //     cout << endl;

    // }



    return 0;

}