#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define all(x) std::begin(x), std::end(x)
#define isz(x) (int)std::size(x)
const auto io_sync_off = [](){std::ios_base::sync_with_stdio(0);std::cin.tie(0);return 0;}();
// Debug defines:
#define watch(x) std::cerr << std::setw(12) << #x << " = " << std::setw(12) << x
#define watchln(x) watch(x) << std::endl
#define watchsp(x) watch(x) << " "
#define cerr cerr && debug && std::cerr
// Defines:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
// Comparators:
template<typename A, typename B> bool operator >(const A& a, const B& b) { return b < a; }
template<typename A, typename B> bool operator<=(const A& a, const B& b) { return !(a > b); }
template<typename A, typename B> bool operator>=(const A& a, const B& b) { return !(a < b); }
template<typename A, typename B> bool operator!=(const A& a, const B& b) { return a < b || b < a; }
template<typename A, typename B> bool operator==(const A& a, const B& b) { return !(a != b); }
namespace std {
#if __cplusplus < 201703L
    // Containers:
    template <typename T> constexpr auto size(const T& t) -> decltype(t.size()) { return t.size(); }
#endif
    // 2D arrays:
    template<typename T, int N, int M> auto size(const T (&)[N][M]) { return N * M; }
    template<typename T, int N, int M> auto begin(T (&a)[N][M]) { return &a[0][0]; }
    template<typename T, int N, int M> auto end(T (&a)[N][M]) { return &a[0][0] + N * M; }
    // 3D arrays:
    template<typename T, int N, int M, int K> auto size(const T (&)[N][M][K]) { return N * M * K; }
    template<typename T, int N, int M, int K> auto begin(T (&a)[N][M][K]) { return &a[0][0][0]; }
    template<typename T, int N, int M, int K> auto end(T (&a)[N][M][K]) { return &a[0][0][0] + N * M * K; }
    // Algorithms:
    template<typename C> void reuniq(C& c) { c.erase(unique(all(c)), end(c)); }
    template<typename C, typename X> int lowpos(const C& c, X x) {
        return int(lower_bound(all(c), x) - begin(c));
    }
    template<typename C, typename X> int uppos(const C& c, X x) {
        return int(upper_bound(all(c), x) - begin(c));
    }
    template<typename X, typename Y> X& remin(X& x, const Y& y) { return x = (y < x) ? y : x; }
    template<typename X, typename Y> X& remax(X& x, const Y& y) { return x = (x < y) ? y : x; }
}
// Numeric:
namespace Numeric {
    template<typename T, typename N> 
    T pow(T a, N n) {
        T r(1);
        while (n > 0) {
            if (n & 1) { r *= a; }
            a *= a; n >>= 1;
        }
        return r;
    }
    template<int mod>
    struct IntMod {
        int value;
        IntMod(int value_ = 0) : value(value_) {
            if (value >= mod) value -= mod;
            if (value < 0) value += mod;
        }
        IntMod& operator+=(IntMod num) {
            value += num.value;
            if (value >= mod) value -= mod;
            return *this;
        }
        IntMod& operator-=(IntMod num) {
            value -= num.value;
            if (value < 0) value += mod;
            return *this;
        }
        IntMod operator+(IntMod num) const { return IntMod(*this) += num; }
        IntMod operator-(IntMod num) const { return IntMod(*this) -= num; }
        IntMod operator*(IntMod num) const { return IntMod(int(value * 1LL * num.value % mod)); }
        IntMod& operator*=(IntMod num) { return *this = *this * num; }
        IntMod operator/(IntMod num) const { return *this * pow(num, mod-2); }
        IntMod& operator/=(IntMod num) { return *this = *this / num; }
    };
    template<int mod> bool operator<(IntMod<mod> a,IntMod<mod> b) { return a.value < b.value; }
    template<int mod>
    std::ostream& operator<<(std::ostream& os, const IntMod<mod>& num) {
        return os << num.value;
    }
}
// Rand:
namespace Rand {
    const auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 gen(seed ^ ull(new ull));
}
// Hash:
namespace Hash {
    const ull mod = (ull(1) << 61) - 1; // prime mod of hashing
    std::vector<ull> pow;
    const int base = [&](){
        pow = {1};
        std::uniform_int_distribution<int> dist((int)1.5e9, (int)2e9);
        int tmp = dist(Rand::gen);
        return tmp % 2 == 0 ? tmp - 1 : tmp;
    }();
    
    struct PolyHash {
        // -------- Static functions --------
        static inline ull add(ull a, ull b) {
            // Calculate (a + b) % mod, 0 <= a < mod, 0 <= b < mod
            return (a += b) < mod ? a : a - mod;
        }
        
        static inline ull sub(ull a, ull b) {
            // Calculate (a - b) % mod, 0 <= a < mod, 0 <= b < mod
            return (a -= b) < mod ? a : a + mod;
        }

        static inline ull mul(ull a, ull b){
            // Calculate (a * b) % mod, 0 <= a < mod, 0 <= b < mod
            ull l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
            ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
            ull ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
            ret = (ret & mod) + (ret >> 61);
            ret = (ret & mod) + (ret >> 61);
            return ret-1;
        }
        
        // -------- Variables of class --------
        std::vector<ull> pref; // polynomial hash on prefix
        
        // Constructor from string:
        PolyHash(const std::string& s) 
            : pref(s.size()+1u, 0) 
        {
            // Pre-calculate powers of base:
            while (pow.size() <= s.size()) {
                pow.push_back(mul(pow.back(), base));
            }
            // Calculate polinomial hash on prefix:
            for (int i = 0; i < (int)s.size(); ++i) {
                pref[i+1] = add(mul(pref[i], base), s[i]);
            }
        }
        
        // Constructor from vector:
        template<typename T> PolyHash(const std::vector<T>& v) 
            : pref(v.size()+1u, 0) 
        {
            // Pre-calculate powers of base:
            while (pow.size() <= v.size()) {
                pow.push_back(mul(pow.back(), base));
            }
            // Calculate polinomial hash on prefix:
            for (int i = 0; i < (int)v.size(); ++i) {
                pref[i+1] = add(mul(pref[i], base), v[i]);
            }
        }
        
        // Get hash from [pos, pos+len-1] segment of string
        inline ull operator()(const int pos, const int len) const {
            return sub(pref[pos+len], mul(pref[pos], pow[len]));
        }
    };
}
// Input:
template<typename T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (auto &it : vec) is >> it;
    return is;
}
// Output:
template<typename A, typename B> std::ostream& operator<<(std::ostream& os, const std::pair<A,B>& pt) {
    return os << "{" << pt.first << ", " << pt.second << "}";
}
template<typename Iterator>
std::ostream& print_range(std::ostream& os, Iterator begin, Iterator end) {
    os << "{";
    for (auto it = begin; it != end; it++) {
        if (it != begin) { os << ", "; }
        os << *it;
    }
    return os << "}";
}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    return print_range(os, vec.begin(), vec.end());
}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& set) {
    return print_range(os, set.begin(), set.end());
}
// Variables:
const int debug = 0, INF = (int)1e9+7, MAX = (int)1e4;
// -----------------------------------------------------------------------------
int main() {
    // solution
    int h, n;
    std::cin >> h >> n;
    vi cost(1+MAX, INF);
    for (int i = 0; i < n; i++) {
        int v, c; std::cin >> v >> c;
        std::remin(cost[v], c);
    }
    vi dp(1+h, INF);
    dp[0] = 0;
    for (int i = 1; i <= h; i++) {
        for (int v = MAX; v >= 1; v--) {
            std::remin(dp[i], dp[std::max(0,i-v)] + cost[v]);
        }
    }
    std::cout << dp[h] << std::endl;
    return 0;
}

Measured memory_bytes: 512