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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;



ll C(int n, int r) {

    if(r > n - r) r = n - r; 

    ll ans = 1;

    int i;



    for(i = 1; i <= r; i++) {

        ans *= n - r + i;

        ans /= i;

    }



    return ans;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    int ma = *max_element(a.begin(), a.end());

    int nh = h+ma;

    imat dp(nh, ivec(n));

    dp[0][0] = 0;

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

    for (int i = 1; i < nh; i++) dp[i][0] = b[0] * ( 1 + (i)/a[0] - !((i) % a[0]));

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

        for (int j = 1; j < n; j++) dp[i][j] = fmin(dp[i][j-1], dp[fmax(i-a[j], 0)][j] + b[j]);

    }

    int ans = 100000001;

    for (int i = h; i < nh; i++) ans = fmin(ans, dp[i][n-1]);

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

}


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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;



ll C(int n, int r) {

    if(r > n - r) r = n - r; 

    ll ans = 1;

    int i;



    for(i = 1; i <= r; i++) {

        ans *= n - r + i;

        ans /= i;

    }



    return ans;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    int ma = *max_element(a.begin(), a.end());

    int nh = h+ma;

    imat dp(nh, ivec(n));

    dp[0][0] = 0;

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

    for (int i = 1; i < nh; i++) dp[i][0] = b[0] * ( 1 + (i)/a[0] - !((i) % a[0]));

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

        for (int j = 1; j < n; j++) dp[i][j] = fmin(dp[i][j-1], dp[fmax(i-a[j], 0)][j] + b[j]);

    }

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

}

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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;



ll C(int n, int r) {

    if(r > n - r) r = n - r; 

    ll ans = 1;

    int i;



    for(i = 1; i <= r; i++) {

        ans *= n - r + i;

        ans /= i;

    }



    return ans;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    int ma = *max_element(a.begin(), a.end());

    int nh = h+ma;

    imat dp(h+1, ivec(n));

    dp[0][0] = 0;

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

    for (int i = 1; i < h+1; i++) dp[i][0] = b[0] * ( 1 + (i)/a[0] - !((i) % a[0]));

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

        for (int j = 1; j < n; j++) dp[i][j] = fmin(dp[i][j-1], dp[fmax(i-a[j], 0)][j] + b[j]);

    }

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

}


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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    int ma = *max_element(a.begin(), a.end());

    int nh = h+ma;

    ivec dp(nh);

    dp[0] = 0;

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

        dp[i] = b[0]*(1+i/a[0] - !(i%a[0]));

        for (int j = 1; j < n; j++) dp[i] = fmin(dp[i], dp[fmax(0, i-a[j])] + b[j]);

    }

    cout << *min_element(dp.begin()+h, dp.end()) << endl;

}

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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    //int ma = *max_element(a.begin(), a.end());

    //int nh = h+ma;

    ivec dp(h+1);

    dp[0] = 0;

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

        dp[i] = b[0]*(1+i/a[0] - !(i%a[0]));

        for (int j = 1; j < n; j++) dp[i] = fmin(dp[i], dp[fmax(0, i-a[j])] + b[j]);

    }

    //cout << *min_element(dp.begin()+h, dp.end()) << endl;

    cout << dp[h] << endl;



}

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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = fmin(dp[i], dp[fmax(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



}

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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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

using namespace std;

 

void chmin(int& a, int b){

    a = min(a, b);

}

 

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<int> dp(100000, 1e9);

    dp[0] = 0;

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

        chmin(dp[min(h+A[i], H)], dp[h] + B[i]);

    }

    cout << dp[H] << endl;

    return 0;}

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

using namespace std;



typedef long long ll;

#define pa pair<int, int> 

#define pal pair<long long, long long>

#define pad pair<double, double>

#define pb push_back

#define mp make_pair

#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}



typedef vector<bool> bvec;

typedef vector<int> ivec;

typedef vector<long long> lvec;

typedef vector<double> dvec;

typedef vector<pa> pvec;



typedef vector< vector<bool> > bmat;

typedef vector< vector<int> > imat;

typedef vector<string> svec;

typedef vector< vector<string> > smat;

const ll infll = (1LL << 60) - 1;

const int inf = (1 << 30) - 1;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int  h, n;

    cin >> h >> n;

    ivec a(n), b(n);

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

    ivec dp(h+1, inf);

    dp[0] = 0;

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

        for (int j = 0; j < n; j++) dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j]);

    }

    cout << dp[h] << endl;



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



using namespace std;

using ll=long long;

using ull=unsigned long long;

using pii=pair<int,int>;



#define INF LONG_MAX

#define MOD 1000000007

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

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

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



int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);



  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<ll>>dp(N+1,vector<ll>(H+10001,INT_MAX));

  dp[0][0]=0;

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

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

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

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

    }

  }

  ll ans=LONG_MAX;

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

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

  }

  cout<<ans<<endl;

  return 0;

}




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



using namespace std;

using ll=long long;

using ull=unsigned long long;

using pii=pair<int,int>;



#define INF LONG_MAX

#define MOD 1000000007

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

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

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



int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);



  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<ll>>dp(N+1,vector<ll>(H+1,LONG_MAX/2));

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

    }

  }



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

  return 0;

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

using namespace std;



const int INF = 1000000000;



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);

	}

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

	dp[0][0] = 0;

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

		dp[0][j] = INF;

	}

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

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

			dp.at(i).at(j) = min( dp.at(i - 1).at(j), dp.at(i).at( max(j - a.at(i - 1), 0 ) )+ b.at(i - 1) );

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

		}

	}

	cout << dp.at(n).at(h) << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.2484468480598192x):
/*

 * 3.cpp

 * Copyright (C) 2020 itachi <itachi@itachi-Z510>

 *

 * Distributed under terms of the MIT license.

 */



#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[i] >> b[i];

   }

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

   /* for (auto v:dp) { */

   /*     for (auto val:v) cout << val << ' ';cout << endl; */

   /* } */

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

       dp[0][j] = INT_MAX;

   }

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

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

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

       }

   }

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

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

#include<cmath>

#include<cstdio>

#include<functional>

#include<iomanip>

#include<iostream>

#include<map>

#include<numeric>

#include<queue>

#include<set>

#include<string>

#include<utility>

#include<vector>



using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll MOD = 1000000007;

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

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

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

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

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



int main()

{	

	int H, N;

	cin >> H >> N;



	vector<int> A(N);

	vector<int> B(N);



	rep(i, N) cin >> A[i] >> B[i];



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



	reple(i, 0, N) dp[i][0] = 0;



	rep(i, N)

	{

		reple(j, 0, H)

		{

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

		}

	}



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



	return 0;

}

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

#include<cmath>

#include<cstdio>

#include<functional>

#include<iomanip>

#include<iostream>

#include<map>

#include<numeric>

#include<queue>

#include<set>

#include<string>

#include<utility>

#include<vector>



using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll MOD = 1000000007;

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

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

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

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

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



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; }



int main()

{

	int H, N;

	cin >> H >> N;



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

	rep(i, N) cin >> A[i] >> B[i];



	//dp[i] := 体力をi以下にするために必要な魔力の最小値

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

	dp[0] = 0;



	reple(i, 1, H)

	{

		rep(j, N)

		{

			int h = max(i - A[j], 0);



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

		}

	}



	cout << dp[H] << endl;



	return 0;

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

using namespace std;

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

#define REP(i,p,n) for(int i=p;i<(int)(n);++i)

#define rep(i,n) REP(i,0,n)

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

#define debug(x) cerr << #x << ": " << x << '\n'



typedef long long int Int;

typedef pair<int,int> P;

using ll = long long;

using VI = vector<int>;

template<class T>bool chmax(T &a, const T b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T b) { if (b<a) { a=b; return 1; } return 0; }

const long long INF = 1LL<<60;



int main(){

    ll H,N;

    cin >> H >> N;

    vector<ll> A(N);

    vector<ll> B(N);

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

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

    dp[0][0] = 0;

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

        for(ll 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]);

        }

    }

    ll ans = INF;

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

        chmin(ans,dp[i][H]);

    }*/

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

}

// Faster C++ solution for the same problem (measured speedup: 2.1454056216793136x):


#include<bits/stdc++.h>

using namespace std;

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

#define REP(i,p,n) for(int i=p;i<(int)(n);++i)

#define rep(i,n) REP(i,0,n)

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

#define debug(x) cerr << #x << ": " << x << '\n'



typedef long long int Int;

typedef pair<int,int> P;

using ll = long long;

using VI = vector<int>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const long long 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<ll> dp(H+1,INF);

    dp[0] = 0;

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

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

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

        }

    }

    cout << dp[H] << endl;

}