// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int h, n;

    cin >> h >> n;

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

    int maxe = 0;

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

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

        chmax(maxe, a[i]);

    }

    maxe += 5;



    vector<vector<int>> dp(n + 2, vector<int>(h + maxe, INF));

    dp[0][0] = 0;

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

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

            if(dp[i][j] == INF) continue;

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

            if(i > 0)   chmin(dp[i][j + a[i - 1]], dp[i][j] + b[i - 1]);

        }

    }



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

    //     cerr << i << '\n';

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

    //         if(dp[i][j] == INF) cerr << -1 << ' ';

    //         else    cerr << dp[i][j] << ' ';

    //     }

    //     cerr << endl;

    // }



    int ans = INF;

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

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

            chmin(ans, dp[i][j]);

        }

    }

    cout << ans << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

#include <cstring>

using namespace std;



using ll = long long;

using P = pair<int, int>;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



template<class T>

inline bool chmax(T& x, T y){

    if(x < y){

        x = y;

        return true;

    }

    return false;

}

template<class T>

inline bool chmin(T& x, T y){

    if(x > y){

        x = y;

        return true;

    }

    return false;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int H, N;

    cin >> H >> N;

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

    dp[0] = 0;

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

        int A, B;

        cin >> A >> B;

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

            if(dp[j] == INF)    continue;

            chmin(dp[min(H, j + A)], dp[j] + B);

        }

    }

    cout << dp[H] << endl;

}

// Fastest known solution for this problem: