stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
/**

 * @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;

}


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

 * @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;

}


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

}


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

}

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

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

}


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

}


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

}




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

}




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

}


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

}


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

}


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

}


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

 vector<int> B(N);

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

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

 }



 // i 番目までの魔法からダメージの総和が j になるように選んだときの魔法消費量の総和の最小値

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



 dp[0][0] = 0;



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

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

     if (j <= A[i]) {

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

     } else {

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

     }

   }

 }



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



}

// Optimized solution to the same problem (faster):
// 公式Youtubeより

// INFが大きすぎるとdp[j]+Bが負になってしまうので注意が必要

#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

const int MOD = 1e9 + 7;

const int INF = 1001001001;

// const ll INF = 1000000000000000000LL;



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

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

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

        }

    }

    cout << dp[h] << endl;

    return 0;

    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 int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e8;

  vector<vector<int>> dp(n + 1, vector<int>(mx, INF));

  dp[0][0] = 0;

  rep(i, n) {

    int a, b;

    cin >> a >> b;

    rep(j, mx) {

      if (j - a >= 0) {

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

      } else {

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

      }

    }

  }

  int ans = INF;

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

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

  }

  cout << ans;

  return 0;

}

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



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



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

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

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

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

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

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

    }

  }

  cout << dp[h];

  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 int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dpOld(mx, INF), dpNew(mx, INF);

  dpOld[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    rep(i, mx) {

      if (i - a >= 0) {

        dpNew[i] = min(dpOld[i], dpNew[i - a] + b);

      } else {

        dpNew[i] = dpOld[i];

      }

      dpOld[i] = dpNew[i];

    }

  }

  int ans = INF;

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

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

  }

  cout << ans;

  return 0;

}

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



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



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

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

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

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

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

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

    }

  }

  cout << dp[h];

  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 int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  int mx = h + 10010;

  const int INF = (int)1e9;

  vector<int> dp(mx, INF);

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

    for (int i = a; i < mx; i++) {

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

    }

  }

  int ans = INF;

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

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

  }

  cout << ans;

  return 0;

}

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



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



using namespace std;



using int64 = int64_t;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int h, n;

  cin >> h >> n;

  const int INF = (int)1e9;

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

  dp[0] = 0;

  while (n--) {

    int a, b;

    cin >> a >> b;

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

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

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

    }

  }

  cout << dp[h];

  return 0;

}

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

using namespace std;

using ll = long long;

using vi = vector<int>;

using vl = vector<ll>;

using vvi = vector<vi>;

using vvl = vector<vl>;

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

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

#define rp(i,s,e) for(int i=(s);i<(e);++i)

#define rpz(i,e) rp(i,0,(e))

#define irp(i,s,e) for(int i=(s);i>(e);--i)

#define irpz(i,s) irp(i,(s),-1)

template<class T> T in(){T x;cin>>x;return x;}

// long long a = in<long long>();

template<class T> vector<T> inarr(int s,int e, T init=0){

	vector<T> v;T x;

	rp(i,0,s)v.push_back(init);

	rp(i,s,e){x=in<T>();v.push_back(x);}

	return v;

}

// vi P = inarr<int>(1,N+1,INT_MAX);

// vi P = inarr<int>(0,N);



// #define NMAX 1000000000

int H,N;

string S, T;

using PLL = pair<ll,ll>;

using VP = vector<PLL>;

VP AB;



ll solve(){

	ll ans=0;



	// rp(i,0,AB.size()){

	// 	cout<<i<<" ";

	// 	cout<<AB[i].first<<" "<<AB[i].second<<"\n";

	// }



	ll INF = LLONG_MAX>>2;

	vvl dp(N+1, vl(H+1, INF));

	dp[0][0] = 0;

	rp(i,1,N+1){

		ll mp,hp;tie(hp,mp)=AB[i-1];

		rp(j,0,H+1){

			if(j==0) dp[i][j] = 0;

			if(j-hp>=0) dp[i][j] = min(dp[i-1][j], dp[i][j-hp] + mp);

			else dp[i][j] = min(dp[i-1][j], mp);



		}

	}



	ans = dp[N][H];

	return ans;

}



int main(){

	cin>>H;

	cin>>N;

	rp(i,0,N){

		int a,b;

		cin>>a>>b;

		AB.emplace_back(a,b);

	}

	cout<< solve() <<endl;

}


// Optimized solution to the same problem (faster):
// E - Crested Ibis vs Monster

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#define rp(i,s,e) for(int i=(s);i<(e);++i)

vi A,B;

int H,N;



int solve(){

	int INF = INT_MAX>>2;

	vvi dp(N+1, vi(H+1, INF));

	dp[0][0] = 0;

	rp(i,1,N+1){

		int hp = A[i-1], mp = B[i-1];

		rp(j,0,H+1){

			if(j == 0) dp[i][j] = 0;

			else if(j-hp >= 0) dp[i][j] = min(dp[i-1][j], dp[i][j-hp] + mp);

			else dp[i][j] = min(dp[i-1][j], mp);

		}

	}

	return dp[N][H];

}



int main(){

	cin>>H>>N;

	rp(i,0,N){

		int a,b; cin>>a>>b;

		A.push_back(a);

		B.push_back(b);

	}

	cout<< solve() <<endl;

}

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

#include <bits/stdc++.h>

#define endl "\n"

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

#define SZ(x) ((int)(x).size())

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

using namespace std;

typedef long long ll;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)

{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

namespace you {

    std::string to_string(char val) {

        return std::string(1, val);

        // return std::string{val};

        // you::to_string(char)

    }

}



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(12);



    int h,n;

    cin>>h>>n;

    vector<int> a(n+1);

    vector<int> b(n+1);



    int max_=0;

    rep(i,n){

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

        if(a[i+1]>max_) max_=a[i+1];

    }

    vector<vector<int>> dp(n+1,vector<int>(h+max_,pow(10,9)));



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

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

            if(a[i]<=j){

                if(dp[i][j-a[i]]==pow(10,9)){

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

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

                }else{

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

                }

            }else dp[i][j]=min(dp[i-1][j],dp[i][j]);

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

        }

    }

    int ans=pow(10,9);

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

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

            if(dp[i][j]<ans) ans=dp[i][j];

        }

    }

    cout<<ans<<endl;

    return 0;

}

// Optimized solution to the same problem (faster):
// ABC153-E

#include <bits/stdc++.h>

#define endl "\n"

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

#define e_b emplace_back

#define sz(x) ((int)(x).size())

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

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> ipair;

typedef pair<ll,ll> lpair;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る

{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る

void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る





int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(12);



    ll h,n;

    cin>>h>>n;

    vector<ll> a(n);

    vector<ll> b(n);

    rep(i,n){

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

    }

    ll inf=pow(10,18);

    vector<ll> dp(h+100,inf);

    dp[0]=0;

    rep(i,n){ //使う魔法

        rep(j,h){ //スタート地点

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

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

        }

    }

    cout<<dp[h]<<endl;

    return 0;

}

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

#include <cassert>

typedef long long int ll;

using namespace std;



// @@ !! LIM()



int main(int argc, char *argv[]) {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout << setprecision(20);



  ll H, N; cin >> H >> N;

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

  for (ll i = 0; i < N; i++) cin >> A.at(i) >> B.at(i);

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

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

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

    ll a = A.at(i);

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

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

      ll base = j-a >= 0 ? dp.at(i+1).at(j-a) : 0;

      dp.at(i+1).at(j) = min(dp.at(i).at(j), base + B.at(i));

    }

  }

  cout << dp.at(N).at(H) << endl;



  return 0;

}




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

#include <cassert>

typedef long long int ll;

using namespace std;



// @@ !! LIM(f:updMaxMin)

// --> f:updMaxMin

// ---- inserted function updMaxMin from util.cc

template<typename T>

bool updMax(T& tmax, const T& x) {

  if (x > tmax) { tmax = x; return true;  }

  else          {           return false; }

}

template<typename T>

bool updMin(T& tmin, const T& x) {

  if (x < tmin) { tmin = x; return true;  }

  else          {           return false; }

}

// ---- end updMaxMin

// @@ !! LIM  -- end mark --



int main(/* int argc, char *argv[] */) {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout << setprecision(20);



  ll H, N; cin >> H >> N;

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

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



  ll big = 1e12;

  vector cur(H + 1, big);

  cur[0] = 0;

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

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

      ll g = min(h + A[i], H);

      updMin(cur[g], cur[h] + B[i]);

    }

  }

  cout << cur[H] << endl;



  return 0;

}




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

#include <vector>

typedef long long ll;

using namespace std;

template <class T>

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

  if (a < b) {

    a = b;

    return 1;

  }

  return 0;

}

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

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

    }

  }

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

}

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

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



typedef long long ll;

using namespace std;

const ll INF = 1ll << 60;



int main() {

  int h, n, a, b;

  cin >> h >> n;

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

  dp[0] = 0;



  rep(i, n) {

    cin >> a >> b;

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

  }



  cout << dp[h] << endl;

}

// Fastest known solution for this problem: