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



using namespace std;



const int INF = 1 << 28;



template <typename T>

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

  if (a < b) {

    a = b;

    return true;

  }

  return false;

}



template <typename T>

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

  if (a > b) {

    a = b;

    return true;

  }

  return false;

}



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int H, N;

  cin >> H >> N;

  vector<int> AA(N), BB(N);

  vector<pair<double, int>> C(N);

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

    cin >> AA[i] >> BB[i];

    C[i] = make_pair((double)AA[i] / BB[i], i);

  }



  sort(C.begin(), C.end());

  reverse(C.begin(), C.end());



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

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

    int k = C[i].second;

    A[i] = AA[k];

    B[i] = BB[k];

  }



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

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

    dp[i][0] = 0;

  }



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

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

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

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

    }

  }



  cout << dp[N][H] << '\n';

  return 0;

}


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



using namespace std;



const int INF = 1 << 28;



template <typename T>

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

  if (a < b) {

    a = b;

    return true;

  }

  return false;

}



template <typename T>

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

  if (a > b) {

    a = b;

    return true;

  }

  return false;

}



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

  dp[0] = 0;



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

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

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

    }

  }



  cout << dp[H] << '\n';

  return 0;

}


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

#include<vector>

#include<cstring>

#include<unordered_map>

#include<algorithm>

#include<cmath>

#include<queue>

#include<deque>

#include<map>

#include<bitset>

#include<random>



using namespace std;

using ll = long long;



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

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

#define repf(i, m, n) for(int i = (m);i < (n);i++)



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

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

//////////////////////////////////////////////////



int h, n;

int a[1010], b[1010];



int main() {

    cin >> h >> n;

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

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

    repf(j, 1, h+1) dp[0][j] = 1000000000;

    rep(i, n) {

        rep(j, h+1) {

            if (j >= a[i])

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

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

            else

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



        }

    }

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

    return 0;

}


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

#include<vector>

#include<cstring>

#include<unordered_map>

#include<algorithm>

#include<cmath>

#include<queue>

#include<deque>

#include<map>

#include<bitset>

#include<random>



using namespace std;

using ll = long long;



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

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

#define repf(i, m, n) for(int i = (m);i < (n);i++)



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

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

//////////////////////////////////////////////////



int h, n;

int a[1010], b[1010];



int main() {

    cin >> h >> n;

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

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

    dp[0] = 0;

    rep(i, n) {

        rep(j, h+1) {

            if (j >= a[i])

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

            else

            dp[j] = min(dp[j], dp[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;

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

using ll = long long;

using P = pair<int,int>;

const ll INF = 1e10;

int main()

{

    int h,n;

    cin >> h >> n;

    

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

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

    rep(i,n){

        

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

    }

    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;





    return 0;

}

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

#define LOCAL

using namespace std;

template <typename A, typename B>

ostream& operator <<(ostream& out, const pair<A, B>& a) {

out << "(" << a.first << "," << a.second << ")";

return out;

}

template <typename T, size_t N>

ostream& operator <<(ostream& out, const array<T, N>& a) {

out << "["; bool first = true;

for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";

return out;

}

template <typename T>

ostream& operator <<(ostream& out, const vector<T>& a) {

out << "["; bool first = true;

for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";

return out;

}

template <typename T, class Cmp>

ostream& operator <<(ostream& out, const set<T, Cmp>& a) {

out << "{"; bool first = true;

for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";

return out;

}

template <typename U, typename T, class Cmp>

ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {

out << "{"; bool first = true;

for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";

return out;

}

#ifdef LOCAL

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

#else

#define trace(...) 42

#endif

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

cerr << name << ": " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

const char* comma = strchr(names + 1, ',');

cerr.write(names, comma - names) << ": " << arg1 << " |";

__f(comma + 1, args...);

}

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

using ll = long long;

#define int long long

using P = pair<int,int>;

//#########################################

const int INF = 1e18;

void chmin(int &a,int b){

	if(a > b )a = b;

}

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

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

		}

	}

	// trace(dp);

	cout << dp[h] << endl;

	return 0;

}

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

using namespace std;

#define ll long long

#define l long

#define pb push_back

#define mp make_pair

#define mt make_tuple



ll M = 998244353;

double ep = 1e-6;

const int N = 1e4 + 5;

//ll ans[N][];



int main() {

	// your code goes here

	//ifstream cin("input.txt");

	//ofstream cout("output.txt");

	ios_base::sync_with_stdio(false); 

    cin.tie(NULL); 

	

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

	vector < pair <ll,ll> > v;

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

	{

	    ll p,q; cin>>p>>q; 

	    //q = -q;

	    v.pb(mp(p,q));

	}

	ll ans[h+1][n+1];

	for(int i=1;i<=h;i++) ans[i][0] = 1e9;

	//for(auto it:v) cout<<it.first<<' '<<it.second<<endl;

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

	{

	    //ans[i] = -1e9;

	    for(int j=1;j<=n;j++)

	    {

	        if(v[j-1].first<=i)

	        {

	            //if( ans[i-v[j].first]+v[j].second > 0 )

	            //if( ans[i-v[j].first]==0 ) continue;

	            ans[i][j]=min( ans[i][j-1],ans[i-v[j-1].first][j]+v[j-1].second );

	        }

	        else ans[i][j] = min(ans[i][j-1],v[j-1].second);

	    }

	    //if(ans[i]==-1e9) ans[i]=0;

	}

	//for(int i=h-1;i<2*h;i++) cout<<ans[i]<<' '; cout<<endl;

	

// 	ll k=ans[h-1]; int id=h;

// 	while( ans[id]==k ) id++;

// 	k = ans[id];

// 	for(int i=id;i<N;i++)

// 	{

// 	    k=max( k,ans[i] );

// 	}

	

	cout<<ans[h][n];

	

	

	return 0;

}


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

using namespace std;

#define ll long long

#define l long

#define pb push_back

#define mp make_pair

#define mt make_tuple





int main() {

	// your code goes here

	//ifstream cin("input.txt");

	//ofstream cout("output.txt");

	ios_base::sync_with_stdio(false); 

    cin.tie(NULL); 

	

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

	vector < pair <ll,ll> > v;

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

	{

	    ll p,q; cin>>p>>q; 

	    v.pb(mp(p,q));

	}



    ll ans[h+1]; ans[0]=0;

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

    {

        ans[i]=1e9;

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

        {

            

            if( i>=v[j].first )

            {

                ans[i] = min( ans[i-v[j].first]+v[j].second , ans[i]);

            }

            else ans[i]=min(ans[i],v[j].second);

        }

    }

	

	cout<<ans[h];

	

	

	return 0;

}


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

#include <cstdio>

#include <string>

#include <algorithm>

#include <utility>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <functional>

using namespace std;

typedef long long ll;

typedef vector<ll> vl;

typedef vector<vector<ll>> vvl;

typedef pair<ll, ll> P;

typedef vector<vector<P>> vvP;

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

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

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

#define exout(x) printf("%.10f\n", x)

#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

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

#define rall(a) a.rbegin(), a.rend()

#define pb push_back

#define re0 return 0

const ll mod = 1000000007;

const ll INF = 1e16;

const ll MAX_N = 100010;



int main() {

    ll h, n;

    cin >> h >> n;



    vl a(n), b(n);

    rep(i, n) {

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

    }



    vvl dp(n+1, vl(h+1, INF));  // dp[i+1][j] : i番目の魔法まででjダメージ与えるときの魔力の総和の最小値

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

        }

    }



    out(dp[n][h]);

    re0;

}

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

#include <cstdio>

#include <string>

#include <algorithm>

#include <utility>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <functional>

using namespace std;

typedef long long ll;

typedef vector<ll> vl;

typedef vector<vector<ll>> vvl;

typedef pair<ll, ll> P;

typedef vector<vector<P>> vvP;

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

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

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

#define exout(x) printf("%.10f\n", x)

#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)

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

#define rall(a) a.rbegin(), a.rend()

#define pb push_back

#define re0 return 0

const ll mod = 1000000007;

const ll INF = 1e16;

const ll MAX_N = 100010;



int main() {

    ll h, n;

    cin >> h >> n;



    vl a(n), b(n);

    rep(i, n) {

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

    }



    vl dp(h+1, INF);  // dp[j] : jダメージ与えるときの魔力の総和の最小値

    dp[0] = 0;

    rep(i, n) {

        rep(j, h+1) {

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

        }

    }



    out(dp[h]);

    re0;

}

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

}


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



}


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

}

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



}


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

}


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



}


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

}

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



}


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



}

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



}


// Fastest known solution for this problem: