//Generated at 2020-01-26 20:22:10 UTC+8
//Created by Alphagocc
#if __cplusplus < 201103L
#define ___TR1(x) <tr1/x>
#else
#define ___TR1(x) <x>
#endif
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <clocale>
#include <cmath>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include ___TR1(cstdbool)
#include ___TR1(cstdint)
#include ___TR1(ctgmath)
#include ___TR1(cfenv)
#include ___TR1(cinttypes)
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cstdalign>
#else
#include <tr1/complex>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include ___TR1(array)
#include ___TR1(random)
#include ___TR1(tuple)
#include ___TR1(unordered_map)
#include ___TR1(unordered_set)
#if __cplusplus >= 201103L
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <type_traits>
#include <typeindex>
#endif
#ifdef USE_PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#endif
#define FORCE_INLINE __inline__ __attribute__((always_inline))
class IO
{
    static const int bufSize = 1 << 18;

    char  inBuf[bufSize], outBuf[bufSize];
    char *ip1 = inBuf, *ip2 = inBuf;

    int goodReadBit = 0, op1 = -1, op2 = bufSize - 1;

    FORCE_INLINE int gc()
    {
        return ip1 == ip2 && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin), ip1 == ip2)
                   ? EOF
                   : *ip1++;
    }

    template <typename T>
    FORCE_INLINE void __RI(T &x)
    {
        int ch = gc(), neg = 1;
        x = 0;
        for (; !(isdigit(ch) || ch == '-' || ch == EOF); ch = gc())
            ;
        if (ch == EOF)
        {
            goodReadBit = 0;
            return;
        }
        if (ch == '-') neg = -1, ch = gc();
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
    }
    template <typename T>
    FORCE_INLINE void __RC(T &x)
    {
        unsigned char ch;
        while (isspace(ch = gc()))
            ;
        x = ch;
    }
    FORCE_INLINE void __RS(std::string &x)
    {
        char ch;
        x.clear();
        for (ch = gc(); isspace(ch); ch = gc())
            ;
        if (ch == EOF)
        {
            goodReadBit = 0;
            return;
        }
        for (; !isspace(ch); ch = gc()) x.push_back(ch);
    }

  public:
    // input
    // int types

    FORCE_INLINE void R(short &x) { __RI(x); }
    FORCE_INLINE void R(unsigned short &x) { __RI(x); }
    FORCE_INLINE void R(int &x) { __RI(x); }
    FORCE_INLINE void R(unsigned &x) { __RI(x); }
    FORCE_INLINE void R(long long &x) { __RI(x); }
    FORCE_INLINE void R(unsigned long long &x) { __RI(x); }

    // char types

    FORCE_INLINE void R(char &x) { __RC(x); }
    FORCE_INLINE void R(unsigned char &x) { __RC(x); }

    // string types

    FORCE_INLINE void R(std::string &x) { __RS(x); }

    // easy STL

    template <typename T1, typename T2>
    FORCE_INLINE void R(std::pair<T1, T2> &x)
    {
        R(x.first);
        R(x.second);
    }
    template <typename T>
    FORCE_INLINE void R(std::vector<T> &x)
    {
        for (typename std::vector<T>::iterator it = x.begin(); it != x.end(); ++it) { R(*it); }
    }
    template <typename T, typename... Args>
    FORCE_INLINE void RA(T *a, int n)
    {
        for (int i = 0; i < n; ++i) R(a[i]);
    }
#if __cplusplus >= 201103L
    template <typename T, typename... Args>
    FORCE_INLINE void R(T &x, Args &... args)
    {
        R(x), R(args...);
    }
    template <typename T, typename... Args>
    FORCE_INLINE void RA(T *a, int n, Args... args)
    {
        for (int i = 0; i < n; ++i) RA(a[i], args...);
    }
#endif
  private:
    // output
    char space;

    FORCE_INLINE void pc(const char &x)
    {
        if (op1 == op2) flush();
        outBuf[++op1] = x;
    }
    template <typename T>
    FORCE_INLINE void __WI(T x)
    {
        static char buf[64];
        static int  len = -1;
        if (x >= 0)
        {
            do
            {
                buf[++len] = x % 10 + 48, x /= 10;
            } while (x);
        }
        else
        {
            pc('-');
            do
            {
                buf[++len] = -(x % 10) + 48, x /= 10;
            } while (x);
        }
        while (len >= 0) { pc(buf[len]), --len; }
    }

  public:
    FORCE_INLINE void flush() { fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1; }

    // int types

    FORCE_INLINE void W(const short &x) { __WI(x); }
    FORCE_INLINE void W(const unsigned short &x) { __WI(x); }
    FORCE_INLINE void W(const int &x) { __WI(x); }
    FORCE_INLINE void W(const unsigned &x) { __WI(x); }
    FORCE_INLINE void W(const long long &x) { __WI(x); }
    FORCE_INLINE void W(const unsigned long long &x) { __WI(x); }

    // char types

    FORCE_INLINE void W(const char &x) { pc(x); }

    // string types

    FORCE_INLINE void W(const char *x)
    {
        while (*x != '\0') pc(*(x++));
    }
    FORCE_INLINE void W(const std::string &x) { W(x.c_str()); }

    // easy stl
    template <typename T>
    FORCE_INLINE void W(const std::vector<T> &x)
    {
        for (typename std::vector<T>::const_iterator it = x.begin(); it != x.end(); it++) WS(*it);
        WL();
    }

    FORCE_INLINE void WL() { W('\n'); }
    template <typename T>
    FORCE_INLINE void WL(const T &x)
    {
        W(x), W('\n');
    }
    FORCE_INLINE void WS() { W(' '); }
    template <typename T>
    FORCE_INLINE void WS(const T &x)
    {
        W(x), W(space);
    }
    template <typename T>
    FORCE_INLINE void WA(T *a, int n)
    {
        for (int i = 0; i < n; i++) WS(a[i]);
        WL();
    }
#if __cplusplus >= 201103L
    template <typename T, typename... Args>
    FORCE_INLINE void W(const T &x, const Args &... args)
    {
        W(x), W(space), W(args...);
    }
    template <typename... Args>
    FORCE_INLINE void WL(const Args &... args)
    {
        W(args...), W('\n');
    }
    template <typename T, typename... Args>
    FORCE_INLINE void WA(T *a, int n, Args... args)
    {
        for (int i = 0; i < n; i++) WA(a[i], args...);
    }
#endif
    template <typename T>
    FORCE_INLINE IO &operator>>(T &x)
    {
        R(x);
        return (*this);
    }
    template <typename T>
    FORCE_INLINE IO &operator<<(const T &x)
    {
        W(x);
        return (*this);
    }
    IO() { space = ' '; }
} io;
namespace Alphagocc
{
#if __cplusplus >= 201103L
decltype(std::chrono::high_resolution_clock::now()) tStart;
};
void      TimeBegin() { Alphagocc::tStart = std::chrono::high_resolution_clock::now(); }
long long TimeEnd()
{
    return (std::chrono::high_resolution_clock::now() - Alphagocc::tStart).count();
#endif
} // namespace Alphagocc
#if __cplusplus >= 201103L
std::random_device randomDevice;
std::mt19937       randomGenerator(randomDevice());
#else
std::tr1::random_device randomDevice;
std::tr1::mt19937       randomGenerator(randomDevice());
#endif
using namespace std;
#if __cplusplus < 201103L
using namespace tr1;
#endif
#define REP(i, x, y) for (int i = x; i < y; i++)
const int8_t  INFC = 0x3f;
const int16_t INFS = 0x3f3f;
const int32_t INF  = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;

int dp[int(1e5)];
int main()
{
    int h, n;
    io >> h >> n;
    vector<pair<int, int>> a(n);
    io >> a;
    memset(dp, INFC, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= h; j++)
            dp[j + a[i].first] = min(dp[j + a[i].first], dp[j] + a[i].second);
    }
    io.WL(*min_element(dp + h, dp + int(1e5) - 1));
    io.flush();
    return 0;
}

Measured memory_bytes: 640