#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

struct mint{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){};
    mint operator-() const{
        return mint(-x);
    }
    mint& operator+=(const mint a){
        if((x+=a.x) >= mod) x -= mod;
        return *this;
    } 
    mint& operator-=(const mint a){
        if((x+= mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const{
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const{
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const{
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const{
        if(!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if(1&t) a *= *this;
        return a;
    }

    mint inv() const{
        return pow(mod-2);
    }
    mint& operator/=(const mint a){
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const{
        mint res(*this);
        return res /= a;
    }
};

struct combination{
    vector<mint> fact, ifact;
    combination(int n):fact(n+1), ifact(n+1){
        assert(n < mod);
        fact[0] = 1;
        for(int i=1; i<=n; i++) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for(int i=n; i>=1; i--) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k){
        if(k<0 || k>n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main(){
    int h, n;
    cin >> h >> n;
    
    vi a(n), b(n);
    rep(i, n){
        cin >> a[i];
        cin >> b[i];
    }

    vvi dp(n+1, vi(h+1, -1));
    rep(i, n+1){
        dp[i][0] = 0;
    }

    for(int i=1; i<=n; i++){
        for(int j=0; j<=h; j++){
            //j番目についたら，一個上を見て，上の方が小さければ書き換える
            if(dp[i-1][j]!=-1){ 
                if(dp[i][j]!=-1){
                    dp[i][j] = min(dp[i-1][j], dp[i][j]);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
            //i番目の魔法を使ったとするとdp[i][j+A[i]]の枠にdp[i][j]+B[i]をいれる（ちゃんと比較して．）
            if(dp[i][j]==-1) continue;
            int nj = min(j+a[i-1], h);
            if(dp[i][nj]==-1) dp[i][nj] = dp[i][j]+b[i-1];
            else dp[i][nj] = min(dp[i][nj], dp[i][j]+b[i-1]);
        }
    }

    /*
    rep(i, n+1){
        rep(j, h+1){
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
    */

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

    return 0;
}

Measured memory_bytes: 39424