// Original C++ solution (slower):
#include <bits/stdc++.h>

const int INF = 1e9;

const int MOD = 1e9+7;

const long long LINF = 1e18;

#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;

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

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

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

#define FOREACH(x,a) for(auto& (x) : (a) )

typedef long long ll;

using namespace std;

typedef pair<ll, ll> P;



template<typename T>

void print(const vector<T> &x) {

    int n = x.size();

    rep(i,n) {

        cout << x[i];

        if (i!=n-1) cout<<" ";

        else cout << endl;

    }

}



template<typename T>

void print(const vector<vector<T>> &x) {

    int n = x.size();

    rep(i,n) {

        rep(j,x[i].size()) {

            cout << x[i][j] << " ";

        }

        cout << endl;

    }

}



template<typename T>

void print(const vector<T> &x, int n) {

    rep(i,n) {

        cout << x[i];

        if (i!=n-1) cout<<" ";

        else cout << endl;

    }

}



template<typename T>

void print(const vector<vector<T>> &x, int n, int m) {

    rep(i,n) {

        rep(j,m) {

            cout << x[i][j] << " ";

        }

        cout << endl;

    }

}



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



void input_init() {

    cin.tie(0); ios::sync_with_stdio(false);

}



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

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

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

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

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

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



    rep(i,n) {

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

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

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

        }

    }



    cout << dp[n][h] << '\n';



    return 0;

}

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

const int INF = 1e9;

const int MOD = 1e9+7;

const long long LINF = 1e18;

#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;

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

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

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

#define FOREACH(x,a) for(auto& (x) : (a) )

typedef long long ll;

using namespace std;

typedef pair<ll, ll> P;



template<typename T>

void print(const vector<T> &x) {

    int n = x.size();

    rep(i,n) {

        cout << x[i];

        if (i!=n-1) cout<<" ";

        else cout << endl;

    }

}



template<typename T>

void print(const vector<vector<T>> &x) {

    int n = x.size();

    rep(i,n) {

        rep(j,x[i].size()) {

            cout << x[i][j] << " ";

        }

        cout << endl;

    }

}



template<typename T>

void print(const vector<T> &x, int n) {

    rep(i,n) {

        cout << x[i];

        if (i!=n-1) cout<<" ";

        else cout << endl;

    }

}



template<typename T>

void print(const vector<vector<T>> &x, int n, int m) {

    rep(i,n) {

        rep(j,m) {

            cout << x[i][j] << " ";

        }

        cout << endl;

    }

}



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



void input_init() {

    cin.tie(0); ios::sync_with_stdio(false);

}



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

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

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



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



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

    dp[0] = 0;



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

        rep(i,n) {

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

        }

    }



    cout << dp[h] << '\n';



    return 0;

}

// Fastest known solution for this problem: