stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.1498414086936233x):
#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<int> a(n),b(n);

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

    dp[0] = 0;

    rep(i,n){

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

    }

    rep(i,n){

        rep(j,h+1){

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

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



        }

    }

    cout << dp[h] << endl;

    return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.230197989435856x):
#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;

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

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

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

		}

	}

	cout << dp[h] << endl;

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.2433908589365004x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.6527058309344471x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.286536284190373x):
#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;

}
// 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: 1.0811257208383016x):
#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;

}
// 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: 1.0811257208383016x):
#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;

}
// 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: 1.9598603686695883x):
#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;

}
// 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: 1.9598603686695883x):
#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;

}