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



using namespace std;

using ll =long long;



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

#define rSORT(a) reverse((a).begin(),(a).end())

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

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

#define debug(x)  cerr << #x << " = " << (x) << endl;

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

void coY() {cout <<"Yes"<<endl;}

void coN(){cout <<"No"<<endl;}



const ll INF = 1LL << 60;



//Write From this Line



const int mod = 1e9+7;

int main()

{

//さやかお姉ちゃんの写経コー

	int h , n ;

	cin >> h >> n ;

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

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



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



	dp[0][0] = 0 ;

	rep(i,n){

		rep(j,h+1){

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

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

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

		}

	}

	cout << dp.back().back() << endl;

}


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

using namespace std;

#define modulo 1000000007

#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)

#define Inf 1000000000

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



int main(){

	int n , h ;	

	cin >> h >> n ;	

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

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

	dp[0] = 0 ; 

	rep(i,n)rep(j,h+1)dp[min(j+a[i],h)]=min(dp[min(j+a[i],h)],dp[j]+b[i]);

	cout <<dp[h] << endl;

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

using namespace std;

typedef long long ll;



template<class T> inline bool chmin(T& a, T b) {

  if (a > b) { a = b; return 1; }

  return 0;

}



const ll INF = 1LL << 60;



int main()

{

  ll H; cin >> H;

  ll N; cin >> N;

  vector<ll> A(N);

  vector<ll> B(N);

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

    cin >> A[i];

    cin >> B[i];

  }

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

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

    dp[i][0] = 0;

  }

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

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

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

    }

  }

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



  return 0;

}


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

using namespace std;

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

typedef long long ll;



int main()

{

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

  vector<int> a(n);

  vector<int> b(n);

  rep(i, n) {

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

  }



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

  dp[0] = 0;

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

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

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

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

    }

  }

  cout << dp[h] << endl;



  return 0;

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

#include<vector>

#include<algorithm>

#include<string>

#include<queue>



using namespace std;

#define int long long

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

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

int inf=100000000000000007;

signed main(){

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

  vector<int> a(n);

  vector<int> b(n);

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

  vector<int> dp(2*h+3,inf);

  dp[0]=0;

  rep(i,n){

    a[i]=min(h,a[i]);

    rep(j,2*h+3){

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

    }

  }

  int res=inf;

  for(int i=h;i<2*h+3;i++){

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

  }

  cout<<res<<endl;

  return 0;

}


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

#include<vector>

#include<algorithm>

#include<string>

#include<queue>

#include<cmath>

#include<cstdio>

#include<tuple>

#include<bitset>

#include<map>



using namespace std;

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

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

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

#define ll long long

using lint=long long;

typedef pair<int,int> P;

const int inf=1000000007;

const int MOD=1000000007;

signed main(){

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

  vector<int> a(n);

  vector<int> b(n);

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

  vector<int> dp(h+5,inf);

  dp[0]=0;

  rep(i,n){

      rep(j,h){

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

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

      }

  }

  cout<<dp[h]<<"\n";

  return 0;

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

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

using namespace std;

using ll = long long;



vector<int> memo;

int n;

int f(int h, const vector<int> a, const vector<int> b){

  if(h <= 0) return 0;

  int mmin = 100000000;

  int karimin;

  rep(i,n){

    if(h-a[i]-1 >=0 && memo[h-a[i]-1]!=0){

      karimin = b[i] + memo[h-a[i]-1];

    }else{

      karimin = b[i] + f(h-a[i],a,b);

    }

    mmin = min(karimin, mmin);

  }

  memo[h-1] = mmin;

  return mmin;

}



int main(){

  int h;

  cin >> h >> n;  

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

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

  

  memo.assign(h,0);

  cout << f(h,a,b) << endl;   

}

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

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

using namespace std;

using ll = long long;



int main(){

  int h, n;

  cin >> h >> n;

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

  dp[0] = 0;

  rep(i,n){

    int a, b;

    cin >> a >> b;

    rep(j,h){

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

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

    }

  }

  cout << dp[h] << endl;

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

#include <string>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <map>

#include <stack>

#include <queue>

#include <set>

#include <cstring>



using namespace std;

// ascending order

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

// descending order

#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())

#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())

#define mp make_pair

#define ts(x) to_string(x)

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

#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)

#define bit(a) bitset<8>(a)

#define des_priority_queue priority_queue<int, vector<int>, greater<int> >

typedef long long ll;

typedef pair<int, int> P;

const ll INF = 1e18;



#define MAX_V 1000000



int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);



  int h, n;

  cin >> h >> n;

  int a[n], b[n];

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



  int dp[n + 1][h + 10001];

  rep(i, 0, n + 1) rep(j, 0, h + 10001) dp[i][j] = 1<<29;

  dp[0][0] = 0;



  rep(i, 0, n) {

    rep(j, 0, h + 10001) {

      if(j - a[i] >= 0) {

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

      } else {

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

      }

    }

  }

  int rsl = 1<<29;

  rep(j, h, h + 10001) rsl = min(rsl, dp[n][j]);

  cout << rsl << endl;

}


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

#include <string>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <map>

#include <stack>

#include <queue>

#include <set>

#include <cstring>



using namespace std;

// ascending order

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

// descending order

#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())

#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())

#define mp make_pair

#define ts(x) to_string(x)

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

#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)

#define bit(a) bitset<8>(a)

#define des_priority_queue priority_queue<int, vector<int>, greater<int> >

typedef long long ll;

typedef pair<int, int> P;

const ll INF = 1e18;



#define MAX_V 1000000



int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);



  int h, n;

  cin >> h >> n;

  int a[n], b[n];

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



  int dp[n + 1][h + 1];

  rep(i, 0, n + 1) rep(j, 0, h + 1) dp[i][j] = 1<<29;

  dp[0][0] = 0;



  rep(i, 0, n) {

    rep(j, 0, 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;

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

using namespace std;



#define INF_LL (int64)1e18

#define INF (int32)1e9

#define REP(i, n) for(int64 i = 0;i < (n);i++)

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

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

#define fs first

#define sc second



using int32 = int_fast32_t;

using uint32 = uint_fast32_t;

using int64 = int_fast64_t;

using uint64 = uint_fast64_t;

using PII = pair<int32, int32>;

using PLL = pair<int64, int64>;



const double eps = 1e-10;



template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}

template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}



template<typename T>

vector<T> make_v(size_t a){return vector<T>(a);}



template<typename T,typename... Ts>

auto make_v(size_t a,Ts... ts){

	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));

}



template<typename T,typename U,typename... V>

typename enable_if<is_same<T, U>::value!=0>::type

fill_v(U &u,const V... v){u=U(v...);}



template<typename T,typename U,typename... V>

typename enable_if<is_same<T, U>::value==0>::type

fill_v(U &u,const V... v){

	for(auto &e:u) fill_v<T>(e,v...);

}



int main(void){

	cin.tie(0);

	ios::sync_with_stdio(false);

	int64 H, N;

	cin >> H >> N;

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

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

	auto dp = make_v<int64>(N+1, H+1);

	fill_v<int64>(dp, INF_LL);

	dp[0][H] = 0;

	REP(i, N) {

	  for (int64 j = H; j >= 0; j--) {

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

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

	  }

	}

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

}


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

using namespace std;



using i64 = long long;



const i64 inf_64 = (i64)1e18;



int main() {

  i64 H, N;

  cin >> H >> N;

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

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

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

  }



  vector<i64> dp(H+1, inf_64);



  dp[H] = 0;



  for (int i = H; i > 0; i--) {

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

      i64 hp = max(i - A[j], (i64)0);

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

    }

  }

  cout << dp[0] << endl;

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



// typedef long long int ll;

// using namespace std;



// int main()

// {



//     ll H, N;

//     cin >> H >> N;



//     ll inf = 999999999;



//     vector<ll> A(N), B(N);



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



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

//     {



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

//     }



//     dp[0] = 0;



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

//     {



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

//         {



//             int nj = min(j + A[i], H);

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

//         }

//     }



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

// return 0;

// }



#include <bits/stdc++.h>



typedef long long int ll;

using namespace std;



int main()

{



    int H, N;

    cin >> H >> N;



    int inf = 999999999;



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



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



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

    {



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

        

    }





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

    {



        dp[0][i] = 0;

        

    }

   



    for (int j = 0; j  <= min(A[0],H); j++)

    {



        dp[j][1] = B[0];

        

    }

  



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

    {



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

        {



            if (j > A[i])

            {

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

            }

            else{



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

            }

        }

    }

  



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

    return 0;

}

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

typedef long long int ll;



using namespace std;

const double PI = 3.14159265358979323846;



int main()

{



    int H, N;

    cin >> H >> N;



    vector<int> A(N);

    vector<int> B(N);



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

    {



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

    }



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



    for (int i = 0; i <= min(A[0],H); i++)

    {

        dp[1][i] = B[0];

    }



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

    {

        dp[i][0] = 0;

    }



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

    {



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

        {



            if (j >= A[i])

            {

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

            }

            else

            {



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

            }

        }

    }



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



    return 0;

}
// Slower C++ solution:
/**

 * @copyright (c) 2020 Daisuke Hashimoto

 */



#include <bits/stdc++.h>

using namespace std;

using ll = int64_t;

using Pair = pair<int64_t, int64_t>;



// std::cout << std::setprecision(20) << 1.1 << endl;



int main() {

  cin.tie(0);

  ios::sync_with_stdio(false);



  int64_t H, N;

  cin >> H >> N;

  // const int64_t L = static_cast<int64_t>(T.length());

  vector<int64_t> A(N + 1);

  vector<int64_t> B(N + 1);

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

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

  }

  const int64_t max_damage = *max_element(A.begin(), A.end());

  vector<vector<int64_t>> mp(N + 1, vector<int64_t>(H + max_damage + 1, INT64_MAX));

  for (auto &a : mp) {

    a[0] = 0;

  }

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

    for (int64_t d = 1; d <= H + max_damage - 1; ++d) {

      mp[i][d] = mp[i - 1][d];

      if (d - A[i] >= 0 && mp[i - 1][d - A[i]] != INT64_MAX) {

        mp[i][d] = min(mp[i][d], mp[i - 1][d - A[i]] + B[i]);

      }

      if (d - A[i] >= 0 && mp[i][d - A[i]] != INT64_MAX) {

        mp[i][d] = min(mp[i][d], mp[i][d - A[i]] + B[i]);

      }

    }

  }

  int64_t result = INT64_MAX;

  for (int64_t d = H; d < H + max_damage; ++d) {

    result = min(result, mp[N][d]);

  }

  cout << result << endl;

  return 0;

}


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

 * @copyright (c) 2020 Daisuke Hashimoto

 */



#include <bits/stdc++.h>

using namespace std;

using ll = int64_t;

using Pair = pair<int64_t, int64_t>;



// std::cout << std::setprecision(20) << 1.1 << endl;



constexpr int64_t kInf = INT64_MAX / 2L;



int main() {

  cin.tie(0);

  ios::sync_with_stdio(false);



  int64_t H, N;

  cin >> H >> N;

  // const int64_t L = static_cast<int64_t>(T.length());

  vector<int64_t> total_mp(H + 1, kInf);

  total_mp[0] = 0;

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

    int64_t damage, mp;

    cin >> damage >> mp;

    for (int64_t d = 0; d < H; ++d) {

      const int64_t next_daname = min(H, d + damage);

      total_mp[next_daname] = min(total_mp[next_daname], total_mp[d] + mp);

    }

  }

  cout << total_mp[H] << endl;

  return 0;

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

#include <vector>

#include <algorithm>

using namespace std;



int main()

{

    int h,n;

    cin >> h >> n;

    int a[n] = {};

    int b[n] = {};

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

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

    dp[0][0] = 0;

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

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

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

            int t = min(h, w+a[i]);

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

        }

    }

    cout << dp[n][h];

    return 0;

}


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

#include <vector>

using namespace std;



int main()

{

    int h,n;

    cin >> h >> n;

    int a[n] = {};

    int b[n] = {};

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

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

    dp[0] = 0;

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

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

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

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

        }

    }

    cout << dp[h] << endl;

    return 0;

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

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

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

using namespace std;

const long long MOD = 1e9 + 7;

const long long INF = 1e12;

const int inf = 1e9;

typedef long long ll;

typedef pair<ll,int> P;

typedef set<int> S;

int h,n;

int main(){

    cin>>h>>n;

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

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

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

    //配るDP

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

    //for(int j=0;j<=)

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

        if(i!=0){

            for(int j=0;j<h+1;j++) dp[i][j]=min(dp[i][j],dp[i-1][j]);

        }

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

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

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

        }

    }

    /*

    rep(i,n+1){

        rep(j,h+1) cout<<dp[i][j]<<" ";

        cout<<endl;

    }*/

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

    return 0;

}


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

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

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

using namespace std;

const long long MOD = 1e9 + 7;

const long long INF = 1e12;

const int inf = 1e9;

typedef long long ll;

typedef pair<ll,int> P;

typedef set<int> S;

int h,n;

int main(){

    cin>>h>>n;

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

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

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

    //配るDP

    dp[0]=0;

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

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

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

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

        }

    }

    /*

    rep(i,n+1){

        rep(j,h+1) cout<<dp[i][j]<<" ";

        cout<<endl;

    }*/

    cout<<dp[h]<<endl;

    return 0;

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

#include<vector>

#include<string>

#include<deque>

#include<unordered_map>

#include<unordered_set>

#include<queue>

#include<algorithm>

#include<cmath>

#include<numeric>

using namespace std;

typedef long long LL;



const int MOD = 1e9+7;



int dfs(vector<int> &dp,int h,vector<vector<int>>&table){

    if(h<=0) return 0;

    if(dp[h]!=-1) return dp[h];

    int cnt  = MOD;

    for(auto item:table){

        cnt = min(cnt,dfs(dp,h-item[0],table)+item[1]);

    }

    dp[h] = cnt;

    return dp[h];

}

void solve(){

    int h,n;

    cin>>h>>n;

    vector<vector<int>> table(n,vector<int>(2,0));

    for(int i=0;i<n;i++) cin>>table[i][0]>>table[i][1];

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

    dp[0]= 0;

    cout<<dfs(dp,h,table)<<endl;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int T = 1;

    // cin>>T;

    while(T--){

        solve();

    }

    return 0;

}




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

#include<vector>

#include<string>

#include<deque>

#include<unordered_map>

#include<unordered_set>

#include<queue>

#include<algorithm>

#include<cmath>

#include<numeric>

using namespace std;

typedef long long LL;



const int MOD = 1e9+7;



int dfs(vector<int> &dp,int h,vector<vector<int>>&table){

    if(h<=0) return 0;

    if(dp[h]!=-1) return dp[h];

    int cnt  = MOD;

    for(auto item:table){

        cnt = min(cnt,dfs(dp,h-item[0],table)+item[1]);

    }

    dp[h] = cnt;

    return dp[h];

}

void solve(){

    int h,n;

    cin>>h>>n;

    vector<vector<int>> table(n,vector<int>(2,0));

    for(int i=0;i<n;i++) cin>>table[i][0]>>table[i][1];

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

    dp[0] = 0;

    // dp[0]= 0;

    // cout<<dfs(dp,h,table)<<endl;

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

        for(auto &item:table){

            int mm = min(h,item[0]+i);

            dp[mm] = min(dp[mm],dp[i]+item[1]);

        }

    }

    cout<<dp[h]<<endl;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int T = 1;

    // cin>>T;

    while(T--){

        solve();

    }

    return 0;

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

#define inf INT_MAX

using namespace std;



int h, n, dp[40001], a[1001], b[1001], dif, rez = inf;



int main()

{

    cin >> h >> n;

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

    {

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

    }

    memset(dp, 63, sizeof(dp));

    dp[h] = 0;

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

    {

        for (int j = h; j >= 0; --j)

        {

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

        }

        rez = min(rez, dp[0]);

    }

    cout << rez;

    return 0;

}


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

#define inf 1111111111

using namespace std;



int h, n, dp[40001], a[1001], b[1001], dif, rez = inf;



int main()

{

    cin >> h >> n;

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

    {

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

    }

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



    dp[h] = 0;

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

    {

        for (int j = h; j >= 0; --j)

        {

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

        }

        rez = min(rez, dp[0]);

    }

    cout << rez;

    return 0;

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

#include<cctype>

using namespace std;

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

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

typedef long long int ll;

#define pi 3.1415926535897932384

#define E9 1000000000

#define eps 1e-4

#define pii pair<int,int>





int main(){

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

  pii AB[N];

  rep(i,N) cin >> AB[i].first >> AB[i].second;

  vector<vector<int>> dp(N+1, vector<int>(H+1,1000000000)); // dp[i][h]: i番目までの魔法でhダメージ与えるときの魔力の最小値

  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(j+AB[i].first,H)] = min(dp[i+1][min(j+AB[i].first,H)], dp[i+1][j] + AB[i].second);

    }

  }

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

  









  // cout << fixed << setprecision(10);

  

  return 0;

}


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

#include<cctype>

using namespace std;

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

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

typedef long long int ll;

#define pi 3.1415926535897932384

#define E9 1000000000

#define eps 1e-4

#define pii pair<int,int>





int main(){

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

  pii AB[N];

  rep(i,N) cin >> AB[i].first >> AB[i].second;

  vector<int> dp(H+1,1000000000); // dp[h]: hダメージ与えるときの魔力の最小値

  dp[0] = 0;

  rep(i,N){

    rep(j,H+1){

      dp[min(j+AB[i].first,H)] = min(dp[min(j+AB[i].first,H)], dp[j] + AB[i].second);

    }

  }

  cout << dp[H] << endl;

  









  // cout << fixed << setprecision(10);

  

  return 0;

}