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(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: 1.8127959874545565x):
#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]);

    }

    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.0615083170253223x):
#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;



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



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



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



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



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



}
// 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.1496933761732153x):
#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;}
// 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.1496933761732153x):
#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;}
// 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: 1.98838426904352x):
#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;}