stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.2188191559747503x):
#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;

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

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int h, n;

    cin >> h >> n;

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

    int maxe = 0;

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

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

        chmax(maxe, a[i]);

    }

    maxe += 5;



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

    dp[0][0] = 0;

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

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

            if(dp[i][j] == INF) continue;

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

            if(i > 0)   chmin(dp[i][j + a[i - 1]], dp[i][j] + b[i - 1]);

        }

    }



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

    //     cerr << i << '\n';

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

    //         if(dp[i][j] == INF) cerr << -1 << ' ';

    //         else    cerr << dp[i][j] << ' ';

    //     }

    //     cerr << endl;

    // }



    int ans = INF;

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

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

            chmin(ans, dp[i][j]);

        }

    }

    cout << ans << endl;

}

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

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int h, n;

    cin >> h >> n;

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

    dp[0] = 0;

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

        int a, b;

        cin >> a >> b;

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

            if(dp[j] == INF)    continue;

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

        }

    }

    int ans = INF;

    for(int i = h; i < h + 10005; ++i)  chmin(ans, dp[i]);

    cout << ans << endl;

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

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int h, n;

    cin >> h >> n;

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

    int maxe = 0;

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

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

        chmax(maxe, a[i]);

    }

    maxe += 5;



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

    dp[0][0] = 0;

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

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

            if(dp[i][j] == INF) continue;

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

            if(i > 0)   chmin(dp[i][j + a[i - 1]], dp[i][j] + b[i - 1]);

        }

    }



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

    //     cerr << i << '\n';

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

    //         if(dp[i][j] == INF) cerr << -1 << ' ';

    //         else    cerr << dp[i][j] << ' ';

    //     }

    //     cerr << endl;

    // }



    int ans = INF;

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

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

            chmin(ans, dp[i][j]);

        }

    }

    cout << ans << endl;

}

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

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

#include <cstring>

using namespace std;



using ll = long long;

using P = pair<int, int>;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



template<class T>

inline bool chmax(T& x, T y){

    if(x < y){

        x = y;

        return true;

    }

    return false;

}

template<class T>

inline bool chmin(T& x, T y){

    if(x > y){

        x = y;

        return true;

    }

    return false;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int H, N;

    cin >> H >> N;

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

    dp[0] = 0;

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

        int A, B;

        cin >> A >> B;

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

            if(dp[j] == INF)    continue;

            chmin(dp[min(H, j + A)], dp[j] + B);

        }

    }

    cout << dp[H] << endl;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.4065874657833661x):
#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;

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

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;

}


// Faster C++ solution for the same problem (measured speedup: 1.6946401122458405x):
#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;

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

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;

}


// Faster C++ solution for the same problem (measured speedup: 1.5363108938249317x):
#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;

}
// 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()

{

	//入力

	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;



}


// Faster C++ solution for the same problem (measured speedup: 2.166095601550994x):
#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;



}
// 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()

{

	//入力

	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;



}


// Faster C++ solution for the same problem (measured speedup: 1.2718542419656695x):
#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;

}
// 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()

{

	//入力

	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;



}


// Faster C++ solution for the same problem (measured speedup: 2.0341253548827076x):
#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;

}