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

#include <iostream>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



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;

}



const ll INF = LONG_LONG_MAX / 2;



vector<vector<ll>> dp;

vector<ll> A;

vector<ll> B;



ll solve(int i, int j, const int H, const int N) {

    if (dp[i][j] >= 0) {

        return dp[i][j];

    }



    ll ans = solve(i - 1, j, H, N);

    chmin(ans, solve(i, max(0LL, j - A[i]), H, N) + B[i]);

    dp[i][j] = ans;

    return ans;

}



int main(void) {

    int H, N;

    cin >> H >> N;



    A.resize(N + 1);

    B.resize(N + 1);

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

        int a, b;

        cin >> a >> b;

        A[i + 1] = a;

        B[i + 1] = b;

    }



    dp.resize(N + 1, vector<ll>(H + 1, -1));

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

        dp[0][i] = INF;

    }

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

        dp[i][0] = 0;

    }



    solve(N, H, H, N);



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

    

    return 0;

}


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

#include <cassert>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



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;

}



const int INF = INT_MAX / 2;



// {damage, mp}

vector<pair<int, int>> magics;



vector<vector<int>> dp;



int main(void) {

    int H, N;

    cin >> H >> N;



    magics.resize(N + 1);

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

        int a, b;

        cin >> a >> b;

        magics[i + 1] = {a, b};

    }



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

    dp[0][0] = 0;



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

        auto magic = magics[i + 1];

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

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

            if (j <= magic.first) {

                chmin(dp[i + 1][j], dp[i][0] + magic.second);

            } else {

                chmin(dp[i + 1][j], dp[i][j - magic.first] + magic.second);

                chmin(dp[i + 1][j], dp[i + 1][j - magic.first] + magic.second);

            }

        }

    }



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



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

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

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

    //     }

    //     cout << endl;

    // }



    return 0;

}


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

#include <iostream>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



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;

}



const ll INF = LONG_LONG_MAX / 2;



vector<vector<ll>> dp;

vector<ll> A;

vector<ll> B;



void solve(const int H, const int N) {

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

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

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

            chmin(dp[i][j], dp[i][max(0LL, j - A[i])] + B[i]);

        }

    }

}



int main(void) {

    int H, N;

    cin >> H >> N;



    A.resize(N + 1);

    B.resize(N + 1);

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

        int a, b;

        cin >> a >> b;

        A[i + 1] = a;

        B[i + 1] = b;

    }



    dp.resize(N + 1, vector<ll>(H + 1, -1));

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

        dp[0][i] = INF;

    }

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

        dp[i][0] = 0;

    }



    solve(H, N);



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

    

    return 0;

}


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

#include <cassert>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



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;

}



const int INF = INT_MAX / 2;



// {damage, mp}

vector<pair<int, int>> magics;



vector<vector<int>> dp;



int main(void) {

    int H, N;

    cin >> H >> N;



    magics.resize(N + 1);

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

        int a, b;

        cin >> a >> b;

        magics[i + 1] = {a, b};

    }



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

    dp[0][0] = 0;



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

        auto magic = magics[i + 1];

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

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

            if (j <= magic.first) {

                chmin(dp[i + 1][j], dp[i][0] + magic.second);

            } else {

                chmin(dp[i + 1][j], dp[i][j - magic.first] + magic.second);

                chmin(dp[i + 1][j], dp[i + 1][j - magic.first] + magic.second);

            }

        }

    }



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



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

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

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

    //     }

    //     cout << endl;

    // }



    return 0;

}


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

using namespace std;



int main() {

    int H, N; cin >> H >> N;

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

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



    long long const INF = 1001001001001001001;

    vector<long long> dp(H + 10001, INF);

    dp[0] = 0;

    for(int v=0; v<dp.size(); ++v) {

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

            if(A[i] > v) continue;

            dp[v] = min(dp[v], dp[v - A[i]] + B[i]);

        }

    }



    long long res = INF;

    for(int v=H; v<dp.size(); ++v) {

        res = min(res, dp[v]);

    }

    cout << res << '\n';

}

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

using namespace std;



int main() {

    int H, N; cin >> H >> N;

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

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



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

    dp[0] = 0;

    for(int v=0; v<dp.size(); ++v) {

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

            int n = min(v + A[i], H);

            dp[n] = min(dp[n], dp[v] + B[i]);

        }

    }

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

}

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

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

#define ll long long

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

#define vi vector<int>

using namespace std;

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

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

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

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



int main(){

  cin.tie(0), ios::sync_with_stdio(false);

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

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

  const int INF = 1001001001;

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

  dp[0][0] = 0;

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

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

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

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

  }

  cout << dp[n][h];

  cout << "\n";

  return 0;

}


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

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

#define ll long long

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

#define vi vector<int>

using namespace std;

const int INF = 1001001001;

const int MOD = 1e9+7;

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

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

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

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



int main(){

  cin.tie(0), ios::sync_with_stdio(false);

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

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

  vi dp(h+1,INF);

  dp[0] = 0;

  rep(i,h+1){

    rep(j,n){

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

    }

  }

  cout << dp[h];

  cout << "\n";

  return 0;

}


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

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

using namespace std;

using ll = long long;

using P = pair<int, int>;



const int MAX_VAL = 1e4;

int main() {

    int H, N; cin >> H >> N;

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

    rep(i, N) {

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

    }



    int limit = max(H * 2, MAX_VAL) + 1;

    vector<int> dp(limit, 1e9);

    dp[0] = 0;

    

    rep(i, N) {

        for (int j = A[i]; j < limit; j++) {

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

        }

    }



    int ans = 1e9;

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

        if (dp[i] != 1e9) {

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

        }

    }



    cout << ans << endl;

}


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

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

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

using namespace std;

using ll = long long;

using P = pair<int, int>;

template <typename T> void chmin(T &a, T b) { a = min(a, b); }

template <typename T> void chmax(T &a, T b) { a = max(a, b); }



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);



  int h, n;

  cin >> h >> n;



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

  dp[0] = 0;

  rep(i, 0, n) {

    int a, b;

    cin >> a >> b;

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

      if (j <= a) {

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

      } else {

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

      }

    }

  }



  cout << dp[h] << endl;

}


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

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

using namespace std;

using ll = long long;

using P = pair<int, int>;



const int MAX_VAL = 1e4;

int main() {

    int H, N; cin >> H >> N;

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

    rep(i, N) {

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

    }



    int limit = max(H * 2, MAX_VAL) + 1;

    vector<int> dp(limit, 1e9);

    dp[0] = 0;

    

    rep(i, N) {

        for (int j = A[i]; j < limit; j++) {

            dp[min(j, H)] = min(dp[min(j, H)], dp[j - A[i]] + B[i]);

        }

    }



    cout << dp[H] << endl;

}


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

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

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

using namespace std;

using ll = long long;

using P = pair<int, int>;

template <typename T> void chmin(T &a, T b) { a = min(a, b); }

template <typename T> void chmax(T &a, T b) { a = max(a, b); }



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);



  int h, n;

  cin >> h >> n;



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

  dp[0] = 0;

  rep(i, 0, n) {

    int a, b;

    cin >> a >> b;

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

      if (j <= a) {

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

      } else {

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

      }

    }

  }



  cout << dp[h] << endl;

}


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

using namespace std;

using int64 = long long;

#define int int64

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

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

#define SORT(x) sort(x.begin(), x.end())

#define GSORT(x) sort(x.begin(), x.end(), greater<int>())

#define mk make_pair

#define fi first

#define se second

#define pb push_back

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

#define V(T) vector<T>

typedef pair<int, int> P;

typedef pair<P, P> PP;

typedef vector<int> vi;

typedef vector<vi> vvi;

int max(int a, int b) {if(b>a) return b; else return a;}

int min(int a, int b) {if(b<a) return b; else return a;}





signed main() {

    int h, n;

    cin >> h >> n;



    vi a(n), b(n);

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



    vi dp(1e5, 1e10);

    dp[0] = 0;



    rep(i, n) {

        rep(j, h) {

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

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

        }

    }



    cout << dp[h] << endl;

    

    return 0;

}

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

using namespace std;

using int64 = long long;

#define int int64

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

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

#define SORT(x) sort(x.begin(), x.end())

#define GSORT(x) sort(x.begin(), x.end(), greater<int>())

#define mk make_pair

#define fi first

#define se second

#define pb push_back

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

#define V(T) vector<T>

typedef pair<int, int> P;

typedef pair<P, P> PP;

typedef vector<int> vi;

typedef vector<vi> vvi;

int max(int a, int b) {if(b>a) return b; else return a;}

int min(int a, int b) {if(b<a) return b; else return a;}





signed main() {

    int h, n;

    cin >> h >> n;

    vi a(n), b(n);

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



    vi dp(h+1, 1e10);

    dp[0] = 0;

    rep(i, n) {

        rep(j, h) {

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

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

        }

    }



    cout << dp[h] << endl;

    

    return 0;

}

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

#include <vector>

#include <algorithm>

using namespace std;



int main(){

        int h,n,i,j;

        cin >> h >> n;

        vector<int> a(n+1);

        vector<int> b(n+1);

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

        for(i=1;i<n+1;++i) cin >> a.at(i) >> b.at(i);

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

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

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

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

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

                        else dp.at(i).at(j) = min(b.at(i),dp.at(i-1).at(j));

                }

        }

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

        return 0;

}

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

#include <vector>

#include <algorithm>

using namespace std;



int main(){

        int h,n,i,j,a,b;

        cin >> h >> n;

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

        dp.at(0) = 0;

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

                cin >> a >> b;

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

                        if(j-a<0) dp.at(j) = min(dp.at(j), b);

                        else dp.at(j) = min(dp.at(j-a)+b,dp.at(j));

                }

        }

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

        return 0;

}

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

using namespace std;

typedef long long ll;



ll inf=1e18;



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

      if(j-a[i]>-1) {

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

      }

      else {

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

      }

    }

  }

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

}

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

using namespace std;

typedef long long ll;



ll inf=1e18;



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<ll> dp(h+1,inf);

  dp[0]=0;

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

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

      if(j-a[i]>-1) {

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

      }

      else {

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

      }

    }

  }

  cout << dp[h] << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):




#include<bits/stdc++.h>



#define loop(i,a,b) for(int i=a;i<b;i++) 

#define rep(i,a) loop(i,0,a)



using namespace std;



template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;





const int MAX_H=10000;

const int MAX_N=1000;



int H,N;

int a[MAX_N+10];

int b[MAX_N+10]; 







int main()

{



    cin>>H>>N;

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

    {

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

    }



    vector<vector<long long>> memo(N+1,vector<long long>(H+1,INF));

    memo[0][0]=0;



    //DPループ

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

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

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

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

        }

    }





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

    return 0;

}

// Optimized solution to the same problem (faster):


//https://webbibouroku.com/Blog/Article/atcoder-abc153



#include<bits/stdc++.h>



#define loop(i,a,b) for(int i=a;i<b;i++) 

#define rep(i,a) loop(i,0,a)



using namespace std;



template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;



struct magic

{

    int at;

    int mp;

};



int main(){

    int H,N;

    cin>>H>>N;

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

    dp[0]=0;

    vector<magic> S(N);



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

        cin>>S[i].at>>S[i].mp;

    }



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

    {

        if(dp[i]==INT_MAX) continue;



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

        {

            int next=min(H,i+S[j].at);

            dp[next]=min(dp[next],dp[i]+S[j].mp);

        }

    }



    cout<<dp[H]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>



using namespace std;





template<class T>

bool chmin(T& a, T b) {

    if (a > b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

bool chmax(T& a, T b) {

    if (a < b) {

        a = b;

        return true;

    }

    return false;

}





const long long INF = 1LL<<60;



void solve() {

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

    dp[0][0] = 0;

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

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

        }



        // for (int k = 0; k <= N; k++) {

        //     for (int l = 0; l <= H; l++) {

        //         if (dp[k][l] == INF) cout << -1 << " ";

        //         else cout << " " << dp[k][l] << " ";

        //     }

        //     cout << endl;

        // }

        // cout << endl;

    }



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



    

}





int main() {

    solve();

    return 0;

}

// Optimized solution to the same problem (faster):
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>



using namespace std;





template<class T>

bool chmin(T& a, T b) {

    if (a > b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

bool chmax(T& a, T b) {

    if (a < b) {

        a = b;

        return true;

    }

    return false;

}



const long long INF = 1LL<<60;





void solve() {

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

}





int main() {

    solve();

    return 0;

}

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

using namespace std;

typedef long long ll;

const ll INF = 1e9;

const ll maxh = 5e4 + 10;

const ll maxn = 1010;

ll p[maxn], c[maxn];

ll dp[maxh];



int main()

{

    ll n, h;

    cin>>h>>n;

    for(ll i = 0; i < n; i++) cin>>p[i]>>c[i];

    fill(dp, dp +  maxh, INF);

    dp[0] = 0;

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

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

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

        }

    }

    ll mins = INF;

    for (ll i = h; i < maxh; i++) mins = min(mins, dp[i]);

    cout<<mins;

    return 0;

}

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

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

#define f1(i,n) for(int i=1;i<=n;i++)

#define f2(i,a,b) for(int i=a;i<=b;i++)

#define sp <<" "                // giving space

#define sp1 <<" "<<              // giving space between two elements

                 // new line

#define M 1000000007              // for mod

#define ll long long

#define ld long double

#define vii vector <pair<int,int>>

#define vll vector <pair<ll,ll>>

#define vi vector <int>

#define vl vector <ll>

#define pb(v,x) v.push_back(x)

#define mp(a,b) make_pair(a,b)

#define F first

#define S second

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define Sort(v) sort(v.begin(),v.end())

using namespace std;

#include <iostream>

#include <bits/stdc++.h>

#include <vector>

#include <numeric>

#include <set>

#include <map>



int dp[100005];

const int inf=100000000;

int main()

{

    int h,n;

    cin>>h>>n;

    int a[n][2];

    f0(i,n)

    cin>>a[i][0]>>a[i][1];

    f1(i,h)

    dp[i]=inf;

    f1(i,h)

    {

        f0(j,n)

        {

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

        }

    }

    cout<<dp[h];

}

// Fastest known solution for this problem: