#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define FOREACH(element, vec_name) for (auto &(element) : (vec_name))
#define VECCIN(vec_name) for (auto &element : (vec_name)) cin >> element

#define ALL(obj) (obj).begin(), (obj).end()

#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)

//dump出力
    // vector
    template <typename T>
    istream &operator>>(istream &is, vector<T> &vec)
    {
        for (T &x : vec)
            is >> x;
        return is;
    }
    // pair
    template <typename T, typename U>
    ostream &operator<<(ostream &os, pair<T, U> &pair_var)
    {
        os << "(" << pair_var.first << ", " << pair_var.second << ")";
        return os;
    }
    // vector
    template <typename T>
    ostream &operator<<(ostream &os, const vector<T> &vec)
    {
        os << "{";
        for (int i = 0; i < vec.size(); i++)
        {
            os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
        }
        os << "}";
        return os;
    }
    // map
    template <typename T, typename U>
    ostream &operator<<(ostream &os, map<T, U> &map_var)
    {
        os << "{";
        repi(itr, map_var)
        {
            os << *itr;
            itr++;
            if (itr != map_var.end())
                os << ", ";
            itr--;
        }
        os << "}";
        return os;
    }
    // set
    template <typename T>
    ostream &operator<<(ostream &os, set<T> &set_var)
    {
        os << "{";
        repi(itr, set_var)
        {
            os << *itr;
            itr++;
            if (itr != set_var.end())
                os << ", ";
            itr--;
        }
        os << "}";
        return os;
    }

    #define DUMPOUT cerr

    void dump_func()
    {
        DUMPOUT << endl;
    }
    template <class Head, class... Tail>
    void dump_func(Head &&head, Tail &&... tail)
    {
        DUMPOUT << head;
        if (sizeof...(Tail) > 0)
        {
            DUMPOUT << ", ";
        }
        dump_func(std::move(tail)...);
    }
    #ifdef DEBUG_
    #define DEB
    #define dump(...)                                                       \
        DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                     \
                << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \
                << endl                                                     \
                << "    ",                                                  \
            dump_func(__VA_ARGS__)
    #else
    #define DEB if (false)
    #define dump(...)
    #endif

using ll = long long;
using P =  pair<int,int>;

const int INF = 1e9;
const int MOD = 1e9+7;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }//最小公倍数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }//最小公倍数

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




int main()
{
    int h,n;
    cin >> h >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> dp(20100,INF);
    rep(i,n) cin >> a[i] >> b[i];

    int ma = *max_element(ALL(a));
    //rep(i,20010) dp[i] = INF;
    dp[0] = 0;
    //rep1(i,ma) dp[i] = 1;

    rep(i,h){
        rep(j,n){
            chmin(dp[i+a[j]], dp[i] + b[j]);
        }
    }

    int ans = INF;
    for(int i=h; i<=h+ma; i++){
        ans = min(ans, dp[i]);
    }

    dump(dp);

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384