stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>



using namespace std;



#define INF 100000000000;



typedef long long ll;



int main() {

    int N, H;

    cin >> H >> N;

    ll *A = new ll[N], *B = new ll[N];

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

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

    ll **dp = new ll*[N+1];

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

        dp[i] = new ll[H+1];

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

            dp[i][j] = INF;

    }

    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], dp[i+1][j-A[i]] + B[i]);

            else

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

            

        }

    }



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



    return 0;

}

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

#include <vector>



using namespace std;



typedef long long ll;

#define INF 10000000000



int main() {

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

    ll *A = new ll[N], *B = new ll[N];

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

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

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

    dp[0] = 0;



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

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

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

        }

    }



    cout << dp[H] << endl;

    return 0;

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

using namespace std;

int main() {

  int h,m,i,j;

  cin>>h>>m;

  vector<int> x(m),y(m)/*,dp(m)*/;

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

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

  for(i=0;i<m;i++) cin>>x[i]>>y[i];

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

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

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

    }

  }

/*  for(i=0;i<=m;i++){

    for(j=0;j<=h;j++) cout<<dp[i][j]<<' ';

    cout<<endl;

  }*/

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

}

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

using namespace std;

int main() {

  int h,m,i,j;

  cin>>h>>m;

  vector<int> x(m),y(m),dp(h+1,1e8);

  dp[0]=0;

  for(i=0;i<m;i++) cin>>x[i]>>y[i];

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

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

      dp[j]=min(dp[j],dp[max(0,j-x[i])]+y[i]);

    }

  }

//  for(j=0;j<=h;j++) cout<<dp[j]<<' ';

  cout<<dp[h]<<endl;

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

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> VECLL;

typedef vector<P> VECP;

typedef priority_queue<P,VECP,greater<P> > PQP;

typedef priority_queue<ll, VECLL, greater<ll> > PQll;



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

#define rrep(i,a,n) for(ll i = n; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue; 

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



int main(){

    ll h,n;

    cin >> h >> n;



    

    ll dp[n+1][h+1] = {};

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

    dp[0][0] = 0;



    ll a[n] = {},b[n] = {};

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



    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;

    return 0;

}


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

using namespace std;



typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<P,ll> PLL;

typedef pair<P,P> PP;

typedef vector<ll> VECLL;

typedef vector<P> VECP;

typedef priority_queue<P,VECP,greater<P> > PQP;

typedef priority_queue<ll, VECLL, greater<ll> > PQll;



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

#define rrep(i,a,n) for(ll i = n; i >= a;i--)

#define index_check(i,n) if(i > n-1 || i < 0) continue; 

#define LINF (ll)1e18

#define INF (int)1e9

#define fs first

#define sc second



int main(){

    ll h,n;

    cin >> h >> n;



    

    ll dp[h+1] = {};

    rep(i,0,h+1) dp[i] = LINF;

    dp[0] = 0;



    ll a[n] = {},b[n] = {};

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



    rep(i,0,n){

        rep(j,0,h+1){

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

        }

    }

    

    cout << dp[h] << endl;

    return 0;

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



using u32 = uint32_t;

using u64 = uint64_t;

using i32 = int32_t;

using i64 = int64_t;



constexpr i64 INF = std::numeric_limits<i64>::max()/2;





struct S {

	i64 a;

	i64 b;

};



int main()

{

	std::ios_base::sync_with_stdio(0);

	

	i64 h, n;



	std::cin >> h >> n;



	std::vector<S> v(n);



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

	{

		i64 a, b;

		std::cin >> a >> b;

		v[i] = {a, b};

	}

	

	i64 dp[h+10005];

	dp[0]=0;

	for(i64 i=1;i<h+10005;++i)

	{

		dp[i]=INF;

	}



	for(i64 i=0;i<h+10005;++i)

	{

		for(i64 j=0;j<n;++j)

		{

			if(v[j].a <= i)

			{

				dp[i] = std::min(dp[i], dp[i-v[j].a]+v[j].b);

			}	

		}

	}



	i64 ans = dp[h];



	for(i64 i=h+1;i<h+10005; ++i)

	{

		if(dp[i] < ans)

		{

			ans = dp[i];

		}

	}



	std::cout << ans << "\n";

	

	return 0;

}

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



using u32 = uint32_t;

using u64 = uint64_t;

using i32 = int32_t;

using i64 = int64_t;



constexpr i64 INF = std::numeric_limits<i64>::max()/2;





struct S {

	i64 a;

	i64 b;

};



int main()

{

	std::ios_base::sync_with_stdio(0);

	

	i64 h, n;



	std::cin >> h >> n;



	std::vector<S> v(n);



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

	{

		i64 a, b;

		std::cin >> a >> b;

		v[i] = {a, b};

	}

	

	i64 dp[h+1];

	dp[0]=0;

	for(i64 i=1;i<h+1;++i)

	{

		dp[i]=INF;

	}



	for(i64 i=0;i<h+1;++i)

	{

		for(i64 j=0;j<n;++j)

		{

			dp[i] = std::min(dp[i], dp[std::max(i-v[j].a, i64(0))]+v[j].b);

		}

	}



	i64 ans = dp[h];



	std::cout << ans << "\n";

	

	return 0;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  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(h, j + a[i])] =

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

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  vi dp(h + 1, 1e9);

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  dp[0][0] = 0;

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

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

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

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  vi dp(h + 1, 1e9);

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  dp[0][0] = 0;

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

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

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

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  vi dp(h + 1, 1e9);

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  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(h, j + a[i])] =

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

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  int dp[h + 1];

  rep(i, h + 1) dp[i] = 1e9;

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  dp[0][0] = 0;

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

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

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

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  int dp[h + 1];

  rep(i, h + 1) dp[i] = 1e9;

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

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

  dp[0][0] = 0;

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

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

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

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

    ni++;

    dp[ni][j] = dp[i][j];

  }

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

}

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

using namespace std;

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

#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)

#define all(n) begin(n), end(n)

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;

using vs = vector<string>;

using vc = vector<char>;

using vb = vector<bool>;

vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};



int main() {

  int h, n;

  cin >> h >> n;

  vi a(n), b(n);

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

  int dp[h + 1];

  rep(i, h + 1) dp[i] = 1e9;

  dp[0] = 0;

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

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

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

  }

  cout << dp[h] << endl;

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

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#define ll long long

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

#define repp(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

using namespace std;

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

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

typedef pair<int,int> P;

typedef pair<ll,ll> Pll;

//小数点以下　cout << fixed << setprecision(10) << num << endl;

//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA

//long*long<0で判定するな

//開区間と閉区間

//アルファベットが何番目かは x=s[i]-'a'

//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ

//切り上げ：(a+(b-1))/b

//32bit以上は 1ull<<j]

// map 初期値0 for(auto itr=mp.begin();itr!=mp.end();++itr) itr->fi itr->se で全探索

// for(auto u:mp) u.fi u.se も可能

//n個のgcd,lcmは一つずつみて更新していく

//大きな数を扱うときは素因数分解した形で持っておく

// (l/a[i]) = l*powmod(a[i],MOD-2)%MOD;

const int INF = 100100100;

int main(){

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

    int a[n],b[n];

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

    ll dp[n+1][30020];

    memset(dp,INF,sizeof(dp));

    dp[0][0]=0;

    rep(i,n){

        rep(j,30020){

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

        }

    }

    ll ans=INF;

    rep(j,30020) if(j>=h) ans=min(ans,dp[n][j]);

    rep(i,n+1){

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

        //cout << endl;

    }

    cout  << ans << endl;

}




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

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#define ll long long

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

#define repp(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

#define ppb pop_back()

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

using namespace std;

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

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

typedef pair<int,int> P;

typedef pair<ll,ll> Pll;



const int INF = 1e9;

signed main(){

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

    int a[n],b[n];

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

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

    rep(i,n+1)rep(j,h+1)dp[i][j]=INF;

    rep(i,n+1)dp[i][0]=0;

    rep(i,n){

        rep(j,h+1){

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

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

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

        }

    }

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

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

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#define ll long long

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

#define repp(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

#define ppb pop_back()

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

using namespace std;

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

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

typedef pair<int,int> P;

typedef pair<ll,ll> Pll;



const int INF = 1e9;

signed main(){

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

    int a[n],b[n];

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

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

    rep(i,n+1)rep(j,h+1)dp[i][j]=INF;

    rep(i,n+1)dp[i][0]=0;

    rep(i,n){

        rep(j,h+1){

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

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

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

        }

    }

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

}


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

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <cmath>

#include <iomanip>

#include <map>

#include <cstring> //memset(dp,0,sizeof(dp))

#include <functional>

#include <cctype>

#include <locale>

#define ll long long

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

#define rrep(i,n) for(int i=n-1;i>=0;i--)

#define fi first

#define se second

#define pb push_back

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

using namespace std;

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

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

typedef pair<int,int> P;

typedef pair<long long,long long> Pll;

#define fout(num) cout << fixed << setprecision(20) << (num) << endl

//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ

//vector<vector<ll>> dp(n,vector<ll>(n))

//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));

//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));



signed main(){

    const int INF = 1e9;

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

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

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

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

        }

    }

    cout << dp[h] << endl;

}