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

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

#define _rep(i, m, n) for(long long int i = m; i < n; i++)

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

//const int N = 1000000;

const ll mod = 1000000007;

using Graph = vector<vector<int>>;

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

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

  

ll gcd(ll A, ll B){

    if(B == 0)return A;

    return gcd(B, A % B);

}

ll lcm(ll A, ll B){

    return A * (B / gcd(A, B));

}

  

/*------------------------------------------------------------------*/

int main(){

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

    vector<ll> a(n);

    vector<ll> b(n);

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

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

    rep(i, n + 1){

        rep(j, h + 1){

            dp[i][j] = 2e8;

        }

    }



    rep(i, n) dp[i][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(j + a[i], h)] = min(dp[i + 1][min(j + a[i], h)], dp[i + 1][j] + b[i]);

        }

    }    

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

}

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

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

#define _rep(i, m, n) for(long long int i = m; i < n; i++)

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const ll mod = 1000000007;

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

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

     

ll gcd(ll A, ll B){

    if(B == 0)return A;

    return gcd(B, A % B);

}

ll lcm(ll A, ll B){

    return A * B / gcd(A, B);

}

template <typename T>

T pow(T a, ll n, T e = 1) {

    T ret = e;

    while (n) {

        if (n & 1) ret *= a;

        a *= a;

        n >>= 1;

    }

    return ret;

}

 

template <int mod>

struct ModInt {

    int x;

    ModInt() : x(0) {}

    ModInt(long long x_) {

        if ((x = x_ % mod + mod) >= mod) x -= mod;

    }

    ModInt& operator+=(ModInt rhs) {

        if ((x += rhs.x) >= mod) x -= mod;

        return *this;

    }

    ModInt& operator-=(ModInt rhs) {

        if ((x -= rhs.x) < 0) x += mod;

        return *this;

    }

    ModInt& operator*=(ModInt rhs) {

        x = (unsigned long long)x * rhs.x % mod;

        return *this;

    }

    ModInt& operator/=(ModInt rhs) {

        x = (unsigned long long)x * rhs.inv().x % mod;

        return *this;

    }

 

    ModInt operator-() const { return -x < 0 ? mod - x : -x; }

    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }

    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }

    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }

    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }

    bool operator==(ModInt rhs) const { return x == rhs.x; }

    bool operator!=(ModInt rhs) const { return x != rhs.x; }

    ModInt inv() const { return pow(*this, mod - 2); }

 

    friend ostream& operator<<(ostream& s, ModInt<mod> a) {

        s << a.x;

        return s;

    }

    friend istream& operator>>(istream& s, ModInt<mod>& a) {

        s >> a.x;

        return s;

    }

};

 

using mint = ModInt<1000000007>;

using Graph = vector<vector<int>>;

Graph G;

/*------------------------------------------------------------------*/

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    

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

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

    ll max_a = 0;

    rep(i, n){

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

        max_a = max(max_a, a[i]);

    }

    vector<ll> dp(h + max_a);

    ll INF = 1e15;

    rep(i, h + max_a) dp[i] = INF;

    dp[0] = 0;

    

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

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

    }

    ll ans = INF;

    _rep(i, h, h + max_a) ans = min(ans, dp[i]);

    cout << ans << endl;

}

// Fastest known solution for this problem: