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



using namespace std;



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    ios::sync_with_stdio(false);



    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q;

    cin >> Q;

    for (size_t i = 0; i < Q; i++)

    {

        int l, r;

        cin >> l >> r;

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

}


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



using namespace std;



int parse_int()

{

    int n = 0, c;

    while (1)

    {

        c = getchar_unlocked();

        if ('0' <= c && c <= '9')

            n = n * 10 + c - '0';

        else

            break;

    }

    return n;

}



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    short ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    // auto M = 100000;

    auto solver = Solver<100000>();



    int Q = parse_int();

    for (size_t i = 0; i < Q; i++)

    {

        int l = parse_int();

        int r = parse_int();

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

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



using namespace std;



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    cin.tie(0);

    ios::sync_with_stdio(false);



    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q;

    cin >> Q;

    for (size_t i = 0; i < Q; i++)

    {

        int l, r;

        cin >> l >> r;

        auto ans = solver.ans[r] - solver.ans[l - 1];

        cout << ans << '\n';

    }

}


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



using namespace std;



int parse_int()

{

    int n = 0, c;

    while (1)

    {

        c = getchar_unlocked();

        if ('0' <= c && c <= '9')

            n = n * 10 + c - '0';

        else

            break;

    }

    return n;

}



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    short ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    // auto M = 100000;

    auto solver = Solver<100000>();



    int Q = parse_int();

    for (size_t i = 0; i < Q; i++)

    {

        int l = parse_int();

        int r = parse_int();

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

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



using namespace std;



int parse_int()

{

    int n = 0, c;

    while (1)

    {

        c = getchar_unlocked();

        if ('0' <= c && c <= '9')

            n = n * 10 + c - '0';

        else

            break;

    }

    return n;

}



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    int ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    constexpr auto M = 100000;

    constexpr auto solver = Solver<M>();

    int Q = parse_int();

    for (size_t i = 0; i < Q; i++)

    {

        int l = parse_int();

        int r = parse_int();

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

}


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



using namespace std;



int parse_int()

{

    int n = 0, c;

    while (1)

    {

        c = getchar_unlocked();

        if ('0' <= c && c <= '9')

            n = n * 10 + c - '0';

        else

            break;

    }

    return n;

}



template <size_t N>

struct Solver

{

    bool is_prime[N + 1];

    short ans[N + 1];

    constexpr Solver() : is_prime(), ans()

    {

        is_prime[0] = false;

        is_prime[1] = false;

        for (size_t i = 2; i <= N; i++)

        {

            is_prime[i] = true;

        }

        for (size_t prime = 2; prime <= N; prime++)

        {

            if (is_prime[prime])

            {

                for (size_t q = prime * 2; q <= N; q += prime)

                {

                    is_prime[q] = false;

                }

            }

        }

        for (size_t i = 1; i <= N; i++)

        {

            ans[i] += ans[i - 1];

            if (is_prime[i] && is_prime[(i + 1) / 2])

            {

                ans[i] += 1;

            }

        }

    }

};



int main()

{

    // auto M = 100000;

    auto solver = Solver<100000>();



    int Q = parse_int();

    for (size_t i = 0; i < Q; i++)

    {

        int l = parse_int();

        int r = parse_int();

        auto ans = solver.ans[r] - solver.ans[l - 1];

        printf("%d\n", ans);

    }

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

using namespace std;

#define ll long long int

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

#define REP(i,s,t) for( int i = s; i <= t; i++ )

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

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int prime[100010];



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    prime[0] = 1;

    prime[1] = 1;

    for(int i = 2; i < 1000; i++) {

        int j = 2;

        while(i * j <= 100000) {

            prime[i*j] = 1;

            j++;

        }

    }

    int sum[100010] = {};

    REP(i, 1, 100000) {

        int flag = 0;

        if (prime[i] == 0 && prime[(i+1)/2] == 0) flag = 1;

        sum[i] = sum[i-1] + flag;

    }



    int Q; cin >> Q;

    int l, r;

    rep(i, Q) {

        cin >> l >> r;

        cout << sum[r] - sum[l-1] << endl;

    }



    return 0;

}


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

using namespace std;

#define ll long long int

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

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

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

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

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



bool isPrime[100010];



void set_prime() {

    rep(i, 100010) isPrime[i] = true;

    isPrime[0] = isPrime[1] = false;

    REP(i, 2, 1000) {

        int j = 2;

        while(i * j <= 100000) {

            isPrime[i * j] = false;

            j++;

        }

    }

}

int sum[100010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    set_prime();

    int Q; cin >> Q;

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

        if (isPrime[i] && isPrime[(i + 1) / 2]) {

            sum[i] = 1;

        }

    }

    rep(i, 100000) sum[i + 1] += sum[i];

    while(Q--) {

        int l, r;

        cin >> l >> r;

        cout << sum[r] - sum[l - 1] << endl;

    }



    return 0;

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

using namespace std;



typedef long long ll;

typedef pair<ll, ll> P;



int Q, l[100001], r[100001];



int main(){

    cin >> Q;

    for(int i=0;i<Q;i++)    cin >> l[i] >> r[i];



    vector<int> nums(100001);

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

        nums[i] = i;

    }



    vector<int> ans;

    for(int i=2;i<=100000;i++){

        if(nums[i] == 0) continue;

        for(int j=2;i*j<=100000;j++){

            nums[i*j] = 0;

        }

        int x = (i + 1) / 2;

        if(nums[x] != 0 && i != 2){

            ans.push_back(i);

        }

    }



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

        auto li = lower_bound(ans.begin(), ans.end(), l[i]);

        auto ri = upper_bound(ans.begin(), ans.end(), r[i]);

        int cnt = ri - li;

        cout << cnt << endl;

    }

}

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

using namespace std;



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

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



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



typedef long long ll;

typedef pair<int, int> P;



const int MAX = 200005;

const int INF = 1001001001;

const int MOD = 1000000007;



bool isPrime(int x) {

    if (x == 1) return false;

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

        if (x % i == 0) return false;

    }

    return true;

}



int main(){

    int Q;

    cin >> Q;



    vector<int> L(Q), R(Q);

    rep(i, Q) cin >> L[i] >> R[i];



    int N = *max_element(R.begin(), R.end());



    vector<int> sum(N+1);

    for (int x = 1; x <= N; ++x) {

        if (isPrime(x) && (x+1) % 2 == 0 && isPrime((x+1)/2)) {

            sum[x] = sum[x-1] + 1;

        } else {

            sum[x] = sum[x-1];

        }

    }



    rep(i, Q) {

        L[i]--;

        cout << sum[R[i]] - sum[L[i]] << endl;

    }

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

#include <iostream>

#include <map>

#include <numeric>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

#include <queue>

#define MOD (1000000007l)

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



using namespace std;



int main(void) {

  vector<bool> primes(100010, true);

  primes[0] = false;

  primes[1] = false;

  for (long i = 2; i < 100010; i++) {

    if (not primes[i]) continue;

    for (long j = i * 2; j < 100010; j += i) primes[j] = false;

  }



  vector<long> accum(100010, 0);

  long count = 0;

  for (long i = 1; i <= 100000; i+= 2) {

    if (primes[i] and primes[(i + 1) / 2]) count++;

    accum[i] = count;

  }



  long Q;

  cin >> Q;



  rep (i, Q) {

    long l, r;

    cin >> l >> r;

    if (l == 1) cout << accum[r] << endl;

    else cout << accum[r] - accum[l-2] << endl;

  }



  return 0;

}


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



bool f[100001];

int c[100002];

int N, L, R ;

int main () {

for (int i = 2; i <= 100000; i ++) if (!f[i]) for(int j = i + i; j <= 100000; j+= i) f[j] = true;

for (int i = 3; i <= 100000; i += 2) if (!f[i] && !f[(i+1)/2]) c[i]++;

for (int i = 3; i <= 100000; i ++) c[i] += c[i-1];

scanf("%d ", &N);

while (N--) {

scanf("%d %d ", &L, &R);

printf("%d\n" , c[R] - c[L-1]);

}

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

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

using Graph = vector<vector<int>>;

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

#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)

#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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

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 long long INF = 1LL << 60;

const int MOD = 1000000007;

const double PI = acos(-1); //3.14~

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//ll dp[110][11100];



int main()

{

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

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

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



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

    dp[0][0] = 0;

    rep(i, n)

    {

        rep(j, h + 1)

        {

            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;



    // rep(i, n + 1)

    // {

    //     COUT(i);

    //     rep(j, h + 1)

    //     {

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

    //     }

    //     cout << endl;

    // }

}

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

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

using Graph = vector<vector<int>>;

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

#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)

#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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

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 long long INF = 1LL << 60;

const int MOD = 1000000007;

const double PI = acos(-1); //3.14~

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//ll dp[110][11100];



int main()

{

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

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

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



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

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

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

            //if (j == 0) cout << dp[j + a[i]] << endl;

        }

    }

    cout << dp[h] << endl;



    // rep(i, h + 1)

    // {

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

    // }

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

using namespace std;



int main(){

  int H,N;

  cin >> H >> N;

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

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

    cin >> A.at(i) >> B.at(i);

  }

  const int64_t INF=1e9;

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

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

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

  }

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

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

      if(j>=A.at(i-1)){

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

      }else{

        dp.at(i).at(j)=min(dp.at(i-1).at(j),(int64_t)B.at(i-1));

      }

    }

  }

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

  return 0;

}


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

using namespace std;



int main(){

  int H,N;

  cin >> H >> N;

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

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

    cin >> A.at(i) >> B.at(i);

  }

  const int64_t INF=1e9;

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

  dp.at(0)=0;

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

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

      if(j>=A.at(i-1)){

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

      }else{

        dp.at(j)=min(dp.at(j),(int64_t)B.at(i-1));

      }

    }

  }

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

  return 0;

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

using namespace std;

typedef struct{

    int A;

    int B;

}MAGIC;

#define INF 1E9;

int main(){

    int H,N;

    cin >> H >> N;

    MAGIC magic[N];

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

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

    }

    int M=magic[0].A;

    MAGIC dp[H+1][N+1];

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

        dp[0][i].A=0;

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

    }

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

        dp[i][0].A=0;

        dp[i][0].B=INF;

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

            if(magic[j-1].A>=i){

                if(dp[i][j-1].B>magic[j-1].B){

                    dp[i][j]=magic[j-1];

                }else if(dp[i][j-1].B==magic[j-1].B){

                    dp[i][j].A=max(dp[i][j-1].A,magic[j-1].A);

                    dp[i][j].B=magic[j-1].B;

                }else{

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

                }

            }else if(i<=dp[i-1][j].A){

                if(dp[i][j-1].B<dp[i-1][j].B){

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

                }else if(dp[i][j-1].B==dp[i-1][j].B){

                    dp[i][j].A=max(dp[i][j-1].A,dp[i-1][j].A);

                    dp[i][j].B=dp[i][j-1].B;

                }else{

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

                }

            }else{

                if(dp[i][j-1].B<dp[i-magic[j-1].A][j].B+magic[j-1].B){

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

                }else if(dp[i][j-1].B==dp[i-magic[j-1].A][j].B+magic[j-1].B){

                    dp[i][j].A=max(dp[i][j-1].A,dp[i-magic[j-1].A][j].A+magic[j-1].A);

                    dp[i][j].B=dp[i][j-1].B;

                }else{

                    dp[i][j].A=dp[i-magic[j-1].A][j].A+magic[j-1].A;

                    dp[i][j].B=dp[i-magic[j-1].A][j].B+magic[j-1].B;

                }

            }

        }

    }

    cout << dp[H][N].B;

    return 0;

}


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

using namespace std;

typedef struct{

    int A;

    int B;

}MAGIC;

#define INF 1E9;

int main(){

    int H,N;

    cin >> H >> N;

    MAGIC magic[N];

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

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

    }

    int dp[H+1][N+1];

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

        dp[0][i]=0;

    }

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

        dp[i][0]=INF;

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

            if(magic[j-1].A>=i){

                if(dp[i][j-1]>magic[j-1].B){

                    dp[i][j]=magic[j-1].B;

                }else{

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

                }

            }else{

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

            }

        }

    }

    cout << dp[H][N];

    return 0;

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

}

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

  }



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

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



  dp[0] = 0;



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

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

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

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

    }

  }



  cout << dp[H] << endl;

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

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1000000007;

const ld PI = acos(-1);  

const ld EPS = 0.0000000001;





int main(){

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

    vector<pair<int, int>> cast(n);

    for(int i=0; i<n; i++)  cin >> cast.at(i).first >> cast.at(i).second;

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

    dp[0][0] = 0;

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

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

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

            dp[i+1][min(j+cast[i].first, h)] = min(dp[i+1][min(j+cast[i].first, h)], dp[i+1][j]+cast[i].second);

        }

    }

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



}




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

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1000000007;

const ld PI = acos(-1);  

const ld EPS = 0.0000000001;

const ll LINF = 1001002003004005006ll;

const int INF = 1001001001;

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

#define repd(i, n) for(ll i=n-1; 0<=i; i--)

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

#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)

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

#define MAX(x) *max_element(ALL(x))

#define MIN(x) *min_element(ALL(x))

int dx[4] = {1, 0, -1, 0};

int dy[4] = {0, 1, 0, -1};





int main(){

    ll h, n;    cin >> h >> n;

    vector<ll> s(n), c(n);

    rep(i, n)   cin >> s[i] >> c[i];

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

    dp[0] = 0;

    rep(i, h){

        rep(j, n){

            ll nv = min(i+s[j], h);

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

        }

    }

    cout << dp[h] << endl;

}