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

#include <array>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <deque>

#include <functional>

#include <iomanip>

#include <iostream>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>



using namespace std;

using ll = long long;

using pint = pair<int, int>;

using pll = pair<ll, ll>;



constexpr double EPS = 1e-7;

constexpr int INF = 1e9;

constexpr ll LINF = 1e18;



#define PI (acos(-1))



constexpr int MOD = 1e9 + 7;



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;

}



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

	cin.tie(nullptr);

	ios::sync_with_stdio(false);

	cout << fixed << setprecision(15);



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

	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;

	return 0;

}


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

#include <array>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <deque>

#include <functional>

#include <iomanip>

#include <iostream>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>



using namespace std;

using ll = long long;

using pint = pair<int, int>;

using pll = pair<ll, ll>;



constexpr double EPS = 1e-7;

constexpr int INF = 1e9;

constexpr ll LINF = 1e18;



#define PI (acos(-1))



constexpr int MOD = 1e9 + 7;



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;

}



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

	cin.tie(nullptr);

	ios::sync_with_stdio(false);

	cout << fixed << setprecision(15);



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

	dp[0] = 0;

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

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

			if (dp[j] == LINF) {

				continue;

			}



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

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

		}

	}

	cout << dp[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;

typedef pair<int,int> P;

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

const int mod = 1000000007;

const int INF = 1001001001;

int main() {

  ll h, n;

  cin >> h >> n;

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

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

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

  dp[0][0] = 0;

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

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

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

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

  }

  

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

}

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

#include<vector>

#include<string>

#include<algorithm>

#include<utility>

#include<cmath>

#include<climits>

#include<queue>

#include<stack>

#include<numeric>

#include<set>

#include<iomanip>

#include<map>

#include<type_traits>

#include<tuple>

#include<deque>

#include<cassert>

using namespace std;

typedef long long ll;

typedef pair<ll,int> P;

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

const int mod = 1000000007;

const int INF = 1001001001;



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, INF));

  dp[0][0] = 0;

  rep(i, n) {

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

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

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

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

    }

  }

  cout << dp[n][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 INF = 1001001001;



int main() {

  int h,n;

  cin >> h >> n;

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



  for(auto& v : ab) {

    cin >> v[0] >> v[1];

  }



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

 rep(j,h+1) {

   dp[0][j] = ((j + ab[0][0] - 1) / ab[0][0])*ab[0][1];

 }



 rep(i,n) {

   rep(j,h+1){

       if (i == 0) continue;

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

     }

 }



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

  return 0;

}


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

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

#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep

#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep

#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep

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



  // range

#define rrng(a) (a).rbegin(),(a).rend() // reverse range

#define isin(x,l,r) ((l) <= (x) && (x) < (r))

#define ru(x,y) (((x)+(y)-1)/(y)) // round up

#define fi first

#define se second

#define eb emplace_back

#define fcout cout << fixed << setprecision(15)





using namespace std;

using ll  = long long;

using P   = pair<int,int>;

using vi  = vector<int>;

using vvi = vector<vi>;

using vp  = vector<P>;

using vl  = vector<ll>;



template<typename T> void Yes(T flag) {

  cout << (flag ? "Yes" : "No") << endl;

}



template<typename T> void pv(vector<T> vec) {

  cout << "[";

  for(auto& v : vec) { cout << v << ","; }

  cout << "]" << endl;

}



template<>

void pv(vector<P> vec) {

  cout << "[";

  for(auto& v : vec) {

    cout << "<" << v.fi << ","<< v.se << ">" << ",";

  }

  cout << "]" << endl;

}



template<typename T> void pv2(vector<vector<T>> vec) {

  for(auto& v : vec) pv(v);

}



int dp[20001];

const int INF = 1001001001;



int main() {

  int h,n;

  cin >> h >> n;

  vi a(n,0),b(n,0);

  int ma=0;

  rep(i,n) {

    cin >> a.at(i) >> b.at(i);

    ma=max(ma,a.at(i));

  }

  rep(i,h+ma) dp[i] = INF;



  dp[0] = 0;

  orep(j,h+ma-1) rep(i,n) {

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

  }

  int ans = INF;

  srep(i,h,h+ma) ans=min(ans,dp[i]);

  cout << ans << 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)

using namespace std;

using ll = long long;

using P = pair<int,int>;



const int INF = 1001001001;



int main() {

  int h,n;

  cin >> h >> n;

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



  for(auto& v : ab) {

    cin >> v[0] >> v[1];

  }



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

 rep(j,h+1) {

   dp[0][j] = ((j + ab[0][0] - 1) / ab[0][0])*ab[0][1];

 }



 rep(i,n) {

   rep(j,h+1){

       if (i == 0) continue;

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

     }

 }



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

  return 0;

}


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

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

#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep

#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep

#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep

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



  // range

#define rrng(a) (a).rbegin(),(a).rend() // reverse range

#define isin(x,l,r) ((l) <= (x) && (x) < (r))

#define ru(x,y) (((x)+(y)-1)/(y)) // round up

#define fi first

#define se second

#define eb emplace_back

#define fcout cout << fixed << setprecision(15)





using namespace std;

using ll  = long long;

using P   = pair<int,int>;

using vi  = vector<int>;

using vvi = vector<vi>;

using vp  = vector<P>;

using vl  = vector<ll>;



template<typename T> void Yes(T flag) {

  cout << (flag ? "Yes" : "No") << endl;

}



template<typename T> void pv(vector<T> vec) {

  cout << "[";

  for(auto& v : vec) { cout << v << ","; }

  cout << "]" << endl;

}



template<>

void pv(vector<P> vec) {

  cout << "[";

  for(auto& v : vec) {

    cout << "<" << v.fi << ","<< v.se << ">" << ",";

  }

  cout << "]" << endl;

}



template<typename T> void pv2(vector<vector<T>> vec) {

  for(auto& v : vec) pv(v);

}



int dp[20001];

const int INF = 1001001001;



int main() {

  int h,n;

  cin >> h >> n;

  vi a(n,0),b(n,0);

  int ma=0;

  rep(i,n) {

    cin >> a.at(i) >> b.at(i);

    ma=max(ma,a.at(i));

  }

  rep(i,h+ma) dp[i] = INF;



  dp[0] = 0;

  orep(j,h+ma-1) rep(i,n) {

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

  }

  int ans = INF;

  srep(i,h,h+ma) ans=min(ans,dp[i]);

  cout << ans << endl;



  return 0;

}


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

{

	//入力

	ll h , n ;

	cin >> h >> n ;

	vector<pair<ll,ll>> p(n);//攻撃力、消費MP

	rep(i,n) cin >> p[i].first >> p[i].second ; 



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

	//	dp[i][j]　i番目までの魔法で、jのダメージを与えるときの消費MPの最小値

	//solve

	//dpをINFで埋める

	rep(i,n) dp[i][0] = 0 ; //0のダメージを与えるときのMPは0



	rep(i,n){

		ll atk = p[i].first ;

		ll mp = p[i].second ;

		rep(j,h+1){

			if(j == 0 ) continue;

			if ( j <= atk ){

				dp[i][j] = mp ;

				if( i != 0 ) chmin(dp[i][j],dp[i-1][j]);

			} else { 

				chmin(dp[i][j],dp[i][j-atk]+mp);

				if( i != 0) chmin(dp[i][j],dp[i-1][j]);

			}

		}

	}

//	rep(i,n){

//		rep(j,h+1){

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

//		}

//		cout << endl;

//	}

//	cout << "above is check" << endl;

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



}


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

{

	//入力

	ll h , n ;

	cin >> h >> n ;//定期の体力はh

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

	dp[0] = 0 ;



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

		ll atk , mp;

		cin >> atk >> mp;

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

			if( i < atk ){

				chmin(dp[i], mp );

			} else {

				chmin(dp[i], dp[i-atk] + mp);

			}

		}

	}

	//rep(j,h+1){

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

	//}

	//cout << endl; 

	//cout <<"above is check" << endl;

	cout << dp[h] << endl;



}


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

}


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

}


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

}


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

}

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



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;   

}

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

}

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

}


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

}


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

}


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

}

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

}

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

}

// Fastest known solution for this problem: