stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

using Graph = vector<vector<int>>;

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

#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)

#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define ALL(a)  (a).begin(),(a).end()

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 long long INF = 1LL << 60;

const int MOD = 1000000007;

const double PI = acos(-1); //3.14~

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//ll dp[110][11100];



int main()

{

    int h, n; cin >> h >> n;

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

    rep(i, n) cin >> a[i] >> b[i];



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

    dp[0][0] = 0;

    rep(i, n)

    {

        rep(j, h + 1)

        {

            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;



    // rep(i, n + 1)

    // {

    //     COUT(i);

    //     rep(j, h + 1)

    //     {

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

    //     }

    //     cout << endl;

    // }

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

using Graph = vector<vector<int>>;

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

#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)

#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define ALL(a)  (a).begin(),(a).end()

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 long long INF = 1LL << 60;

const int MOD = 1000000007;

const double PI = acos(-1); //3.14~

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//ll dp[110][11100];



int main()

{

    int h, n; cin >> h >> n;

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

    rep(i, n) cin >> a[i] >> b[i];



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

    dp[0] = 0;



    rep(i, n)

    {

        rep(j, h + 1)

        {

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

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

            //if (j == 0) cout << dp[j + a[i]] << endl;

        }

    }

    cout << dp[h] << endl;



    // rep(i, h + 1)

    // {

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

    // }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main(){

  int H,N;

  cin >> H >> N;

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

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

    cin >> A.at(i) >> B.at(i);

  }

  const int64_t INF=1e9;

  vector<vector<int64_t> > dp(N+1,vector<int64_t>(H+1,INF));

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

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

  }

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

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

      if(j>=A.at(i-1)){

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

      }else{

        dp.at(i).at(j)=min(dp.at(i-1).at(j),(int64_t)B.at(i-1));

      }

    }

  }

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

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main(){

  int H,N;

  cin >> H >> N;

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

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

    cin >> A.at(i) >> B.at(i);

  }

  const int64_t INF=1e9;

  vector<int64_t> dp(H+1, INF);

  dp.at(0)=0;

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

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

      if(j>=A.at(i-1)){

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

      }else{

        dp.at(j)=min(dp.at(j),(int64_t)B.at(i-1));

      }

    }

  }

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

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef struct{

    int A;

    int B;

}MAGIC;

#define INF 1E9;

int main(){

    int H,N;

    cin >> H >> N;

    MAGIC magic[N];

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

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

    }

    int M=magic[0].A;

    MAGIC dp[H+1][N+1];

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

        dp[0][i].A=0;

        dp[0][i].B=0;

    }

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

        dp[i][0].A=0;

        dp[i][0].B=INF;

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

            if(magic[j-1].A>=i){

                if(dp[i][j-1].B>magic[j-1].B){

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

                }else if(dp[i][j-1].B==magic[j-1].B){

                    dp[i][j].A=max(dp[i][j-1].A,magic[j-1].A);

                    dp[i][j].B=magic[j-1].B;

                }else{

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

                }

            }else if(i<=dp[i-1][j].A){

                if(dp[i][j-1].B<dp[i-1][j].B){

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

                }else if(dp[i][j-1].B==dp[i-1][j].B){

                    dp[i][j].A=max(dp[i][j-1].A,dp[i-1][j].A);

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

                }else{

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

                }

            }else{

                if(dp[i][j-1].B<dp[i-magic[j-1].A][j].B+magic[j-1].B){

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

                }else if(dp[i][j-1].B==dp[i-magic[j-1].A][j].B+magic[j-1].B){

                    dp[i][j].A=max(dp[i][j-1].A,dp[i-magic[j-1].A][j].A+magic[j-1].A);

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

                }else{

                    dp[i][j].A=dp[i-magic[j-1].A][j].A+magic[j-1].A;

                    dp[i][j].B=dp[i-magic[j-1].A][j].B+magic[j-1].B;

                }

            }

        }

    }

    cout << dp[H][N].B;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef struct{

    int A;

    int B;

}MAGIC;

#define INF 1E9;

int main(){

    int H,N;

    cin >> H >> N;

    MAGIC magic[N];

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

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

    }

    int dp[H+1][N+1];

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

        dp[0][i]=0;

    }

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

        dp[i][0]=INF;

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

            if(magic[j-1].A>=i){

                if(dp[i][j-1]>magic[j-1].B){

                    dp[i][j]=magic[j-1].B;

                }else{

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

                }

            }else{

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

            }

        }

    }

    cout << dp[H][N];

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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];

  }



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

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



  dp[0] = 0;



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

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

      int k = min(j + A[i], H);

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

    }

  }



  cout << dp[H] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1000000007;

const ld PI = acos(-1);  

const ld EPS = 0.0000000001;





int main(){

    int h, n;   cin >> h >> n;

    vector<pair<int, int>> cast(n);

    for(int i=0; i<n; i++)  cin >> cast.at(i).first >> cast.at(i).second;

    vector<vector<ll>> dp(n+1, vector<ll>(h+1, 1e+15)); 

    dp[0][0] = 0;

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

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

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

            dp[i+1][min(j+cast[i].first, h)] = min(dp[i+1][min(j+cast[i].first, h)], dp[i+1][j]+cast[i].second);

        }

    }

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



}




// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1000000007;

const ld PI = acos(-1);  

const ld EPS = 0.0000000001;

const ll LINF = 1001002003004005006ll;

const int INF = 1001001001;

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

#define repd(i, n) for(ll i=n-1; 0<=i; i--)

#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)

#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)

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

#define MAX(x) *max_element(ALL(x))

#define MIN(x) *min_element(ALL(x))

int dx[4] = {1, 0, -1, 0};

int dy[4] = {0, 1, 0, -1};





int main(){

    ll h, n;    cin >> h >> n;

    vector<ll> s(n), c(n);

    rep(i, n)   cin >> s[i] >> c[i];

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

    dp[0] = 0;

    rep(i, h){

        rep(j, n){

            ll nv = min(i+s[j], h);

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

        }

    }

    cout << dp[h] << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>



using namespace std;



#define INF 100000000000;



typedef long long ll;



int main() {

    int N, H;

    cin >> H >> N;

    ll *A = new ll[N], *B = new ll[N];

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

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

    ll **dp = new ll*[N+1];

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

        dp[i] = new ll[H+1];

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

            dp[i][j] = INF;

    }

    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], dp[i+1][j-A[i]] + B[i]);

            else

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

            

        }

    }



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



    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>



using namespace std;



typedef long long ll;

#define INF 10000000000



int main() {

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

    ll *A = new ll[N], *B = new ll[N];

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

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

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

    dp[0] = 0;



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

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

            dp[j] = min(dp[j], dp[max(j-A[i], (ll)0)] + B[i]);

        }

    }



    cout << dp[H] << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main() {

  int h,m,i,j;

  cin>>h>>m;

  vector<int> x(m),y(m)/*,dp(m)*/;

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

  for(i=0;i<=m;i++) dp[i][0]=0;

  for(i=0;i<m;i++) cin>>x[i]>>y[i];

  for(i=0;i<m;i++){

    for(j=1;j<=h;j++){

      dp[i+1][j]=min(min(dp[i][j],dp[i][max(0,j-x[i])]+y[i]),dp[i+1][max(0,j-x[i])]+y[i]);

    }

  }

/*  for(i=0;i<=m;i++){

    for(j=0;j<=h;j++) cout<<dp[i][j]<<' ';

    cout<<endl;

  }*/

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

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

int main() {

  int h,m,i,j;

  cin>>h>>m;

  vector<int> x(m),y(m),dp(h+1,1e8);

  dp[0]=0;

  for(i=0;i<m;i++) cin>>x[i]>>y[i];

  for(i=0;i<m;i++){

    for(j=1;j<=h;j++){

      dp[j]=min(dp[j],dp[max(0,j-x[i])]+y[i]);

    }

  }

//  for(j=0;j<=h;j++) cout<<dp[j]<<' ';

  cout<<dp[h]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> VECLL;

typedef vector<P> VECP;

typedef priority_queue<P,VECP,greater<P> > PQP;

typedef priority_queue<ll, VECLL, greater<ll> > PQll;



#define rep(i,a,n) for(ll i = a;i < n;i++)   

#define rrep(i,a,n) for(ll i = n; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue; 

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



int main(){

    ll h,n;

    cin >> h >> n;



    

    ll dp[n+1][h+1] = {};

    rep(i,0,n+1) rep(j,0,h+1) dp[i][j] = LINF;

    dp[0][0] = 0;



    ll a[n] = {},b[n] = {};

    rep(i,0,n) cin >> a[i] >> b[i];



    rep(i,0,n){

        rep(j,0,h+1){

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

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

        }

    }

    

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

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> VECLL;

typedef vector<P> VECP;

typedef priority_queue<P,VECP,greater<P> > PQP;

typedef priority_queue<ll, VECLL, greater<ll> > PQll;



#define rep(i,a,n) for(ll i = a;i < n;i++)   

#define rrep(i,a,n) for(ll i = n; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue; 

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



int main(){

    ll h,n;

    cin >> h >> n;



    

    ll dp[h+1] = {};

    rep(i,0,h+1) dp[i] = LINF;

    dp[0] = 0;



    ll a[n] = {},b[n] = {};

    rep(i,0,n) cin >> a[i] >> b[i];



    rep(i,0,n){

        rep(j,0,h+1){

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

        }

    }

    

    cout << dp[h] << endl;

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using u32 = uint32_t;

using u64 = uint64_t;

using i32 = int32_t;

using i64 = int64_t;



constexpr i64 INF = std::numeric_limits<i64>::max()/2;





struct S {

	i64 a;

	i64 b;

};



int main()

{

	std::ios_base::sync_with_stdio(0);

	

	i64 h, n;



	std::cin >> h >> n;



	std::vector<S> v(n);



	for(i64 i=0; i<n; ++i)

	{

		i64 a, b;

		std::cin >> a >> b;

		v[i] = {a, b};

	}

	

	i64 dp[h+10005];

	dp[0]=0;

	for(i64 i=1;i<h+10005;++i)

	{

		dp[i]=INF;

	}



	for(i64 i=0;i<h+10005;++i)

	{

		for(i64 j=0;j<n;++j)

		{

			if(v[j].a <= i)

			{

				dp[i] = std::min(dp[i], dp[i-v[j].a]+v[j].b);

			}	

		}

	}



	i64 ans = dp[h];



	for(i64 i=h+1;i<h+10005; ++i)

	{

		if(dp[i] < ans)

		{

			ans = dp[i];

		}

	}



	std::cout << ans << "\n";

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using u32 = uint32_t;

using u64 = uint64_t;

using i32 = int32_t;

using i64 = int64_t;



constexpr i64 INF = std::numeric_limits<i64>::max()/2;





struct S {

	i64 a;

	i64 b;

};



int main()

{

	std::ios_base::sync_with_stdio(0);

	

	i64 h, n;



	std::cin >> h >> n;



	std::vector<S> v(n);



	for(i64 i=0; i<n; ++i)

	{

		i64 a, b;

		std::cin >> a >> b;

		v[i] = {a, b};

	}

	

	i64 dp[h+1];

	dp[0]=0;

	for(i64 i=1;i<h+1;++i)

	{

		dp[i]=INF;

	}



	for(i64 i=0;i<h+1;++i)

	{

		for(i64 j=0;j<n;++j)

		{

			dp[i] = std::min(dp[i], dp[std::max(i-v[j].a, i64(0))]+v[j].b);

		}

	}



	i64 ans = dp[h];



	std::cout << ans << "\n";

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vector<vi> dp(n + 1, vi(h + 1, 1e9));

  dp[0][0] = 0;

  rep(i, n) rep(j, h + 1) {

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

    dp[i + 1][min(h, j + a[i])] =

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

  }

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

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vi dp(h + 1, 1e9);

  dp[0] = 0;

  rep(i, n) rep(j, h + 1) {

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

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

  }

  cout << dp[h] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vector<vi> dp(n + 1, vi(h + 1, 1e9));

  dp[0][0] = 0;

  rep(i, n) rep(j, h + 1) {

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

    int ni = i, nj = min(h, j + a[i]);

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vi dp(h + 1, 1e9);

  dp[0] = 0;

  rep(i, n) rep(j, h + 1) {

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

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

  }

  cout << dp[h] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vector<vi> dp(n + 1, vi(h + 1, 1e9));

  dp[0][0] = 0;

  rep(i, n) rep(j, h + 1) {

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

    int ni = i, nj = min(h, j + a[i]);

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

  rep(i, n) cin >> a[i] >> b[i];

  vi dp(h + 1, 1e9);

  dp[0] = 0;

  rep(i, n) rep(j, h + 1) {

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

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

  }

  cout << dp[h] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#define ll long long

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

#define repp(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

#define ppb pop_back()

#define ALL(a) (a).begin(),(a).end()

using namespace std;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

typedef pair<int,int> P;

typedef pair<ll,ll> Pll;



const int INF = 1e9;

signed main(){

    int h,n; cin >> h >> n;

    int a[n],b[n];

    rep(i,n)cin>>a[i]>>b[i];

    int dp[n+1][h+1];

    rep(i,n+1)rep(j,h+1)dp[i][j]=INF;

    rep(i,n+1)dp[i][0]=0;

    rep(i,n){

        rep(j,h+1){

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

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

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

        }

    }

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

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#include <functional>

#include <cctype>

#include <locale>

#define ll long long

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

#define rrep(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

#define ALL(a) (a).begin(),(a).end()

using namespace std;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

typedef pair<int,int> P;

typedef pair<long long,long long> Pll;

#define fout(num) cout << fixed << setprecision(20) << (num) << endl

//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ

//vector<vector<ll>> dp(n,vector<ll>(n))

//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));

//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));



signed main(){

    const int INF = 1e9;

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    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+1){

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

            chmin(dp[x],dp[j]+b);

        }

    }

    cout << dp[h] << endl;

}






// Fastest known solution for this problem: