/**
    Md. Mujahedul Azad (Turin)
    Hajee Mohammad Danesh Science & Technology University **/

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

#define ff              first
#define se              second
#define nl              << '\n'
#define gf              << ' ' <<
#define pb              push_back
#define sq(a)           ((a) * (a))
#define Sort(a)         sort(all(a))
#define sz(x)           (int)x.size()
#define fillVec(a, v)   fill(all(a), v)
#define btz(a)          __builtin_ctz(a)
#define all(v)          v.begin(),v.end()
#define max3(a,b,c)     max(a, max(b, c))
#define min3(a,b,c)     min(a, min(b, c))
#define abs(x)          (((x)<0)?-(x):(x))
#define parity(a)       __builtin_parity(a)
#define maxall(v)       *max_element(all(v))
#define minall(v)       *min_element(all(v))
#define cinIg           cin.sync(); cin.get()
#define countOne(a)     __builtin_popcount(a)
#define mem(a,v)        memset(a, v, sizeof(a))
#define RSort(a)        Sort(a), reverse(all(a))
#define precision(x)    cout << setprecision(x) << fixed
#define un(a)           Sort(a), (a).erase(unique(all(a)),a.end())
#define FasterIO        ios_base::sync_with_stdio(false);cin.tie(NULL)
#define TestCasespp     int cases, tc; cin>>tc; for(cases=1; cases<=tc; cases++)
#define common(a,b)     Sort(a), Sort(b), a.erase(set_intersection(all(a), all(b), a.begin()), a.end())
#define uncommon(a,b)   Sort(a), Sort(b), a.erase(set_symmetric_difference(all(a), all(b), a.begin()), a.end())

/**------- ShortCuts----------*/
typedef long long             ll;
typedef unsigned long long    ull;
typedef double                db;
typedef long double           ldb;
typedef pair<int, int>        pii;
typedef pair<ll, ll>          pll;
typedef pair<int, pii>        iii;
typedef vector<int>           vi;
typedef vector<ll>            vl;
typedef vector<pii>           vii;
typedef vector<iii>           viii;
typedef vector<vi>            vvi;

/**------- Char Chk----------*/
inline bool isLow(char ch){return (ch>='a' && ch<='z');}
inline bool isUpp(char ch){return (ch>='A' && ch<='Z');}
inline bool isDig(char ch){return (ch>='0' && ch<='9');}

/**--------Loops--------------*/
#define frab(i, a, b)           for(__typeof(b) i=(a); i<=(b); i++)
#define fr0(i, n)               frab(i, 0, n-1)
#define fr1(i, n)               frab(i, 1, n)
#define rfab(i, a, b)           for(__typeof(b) i=(b); i>=(a); i--)
#define rf0(i, n)               rfab(i, 0, n-1)
#define rf1(i, n)               rfab(i, 1, n)
#define fra(it, v)              for(auto &it:v)
#define frs(i, s)               fr0(i, s.size())

/**------- Debug Functions ---------*/
template<typename T, typename... args>inline string arrStr(T arr, int n){stringstream s; s << "[ ";for(int i=0; i<n-1; i++)s << arr[i] << ", ";s << arr[n-1] << " ]";return s.str();}
#define EVARS(args...) {__evars_begin(__LINE__); __evars(split(#args, ',').begin(), args);}
inline void __evars_begin(int line) { cout << "#" << line << ": "; }
template<typename T> inline void __evars_out_var(vector<T> val) { cout << arrStr(val, val.size()); }
template<typename T> inline void __evars_out_var(T* val) { cout << arrStr(val, 10); }
template<typename T> inline void __evars_out_var(T val) { cout << val; }
inline void __evars(vector<string>::iterator it) { cout << endl; }
template<typename T, typename... Args>inline void __evars(vector<string>::iterator it, T a, Args... args){cout << it->substr((*it)[0] == ' ', it->length()) << " = ";__evars_out_var(a);cout << "; ";__evars(++it, args...);}
inline vector<string> split(const string &s, char c){vector<string> v; stringstream ss(s); string x;while(getline(ss, x, c))v.emplace_back(x);return move(v);}

template<typename T=long long> T multiply(T a, T b, T mod){T res = 0; a %= mod; b %= mod;while(b){if(b & 0x1) res = (res + a)%mod; b >>= 1; if(a < mod-a) a<<=1; else a -= (mod-a);}return res;}
template<typename T=long long> T power(T val, T p, T mod) { val %= mod; T res = 1; while (p > 0) { if (p & 0x1) res = (res*val)%mod; val = (val*val)%mod; p >>= 1;} return res;}
template<typename T=long long> T power(T val, T p) {T res = 1;while (p > 0){if (p & 0x1) res = (res*val); val = (val*val); p >>= 1;} return res;}
template<typename T=long long> T powerMul(T val, T p, T mod) { val %= mod; T res = 1; while (p > 0) { if (p & 0x1) res = multiply(res, val, mod);val = multiply(val, val, mod); p >>= 1; } return res;}
template<typename T> T gcd(T a, T b){return b==0?a:gcd(b, a%b);}
template<typename T> T lcm(T a, T b){return a/gcd(a,b) * b;}
template<typename T> string toString(T x){stringstream ss; ss<<x; return ss.str();}
template<typename T> T stringToT(string s){T p; istringstream ss(s); ss>>p; return p;}
template<typename T> T SOD(T n){__typeof(n) sum=0, i=1; for(; i*i<=n; i++) sum += (n%i)?0:((sq(i)==n)?i:i+n/i); return sum;}

//#define fun
#ifdef fun
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T, S> &v){os << "(" << v.ff << ", " << v.se << ")";return os;}
template<typename T, typename S> ostream& operator << (ostream& os, const map<T, S> &v){for(auto it : v) os << it.ff << " : " << it.se nl; return os;}
template<typename T>ostream& operator << (ostream& os, const set<T> &v){ os << "["; for(auto it : v){os << it;if(it != *v.rbegin())os << ", ";}os << "]";return os;}
template<typename T>ostream& operator << (ostream& os, const vector<T> &v){os << "["; for(int i=0; i<v.size(); i++){ os << v[i]; if(i != sz(v)-1) os << ", ";} os << "]"; return os;}
#endif // fun

/**--------Range Query-----*/
#define left(p)             (p<<1)
#define right(p)            ((p<<1)|1)
#define mid(l,r)            (l + (r-l)/2)

/**-----------File------------*/
#define inOut              {input; output;}
#define input              freopen("input.txt","r",stdin)
#define output             freopen("output.txt","w",stdout)

/**--------Constant------------*/
#define mx3                1001
#define mx4                10001
#define mx5                100001
#define mx6                1000001
#define INF                0x3f3f3f3f

/**-------Upper & Lower Bound-------*/
#define LB(a, v)            (lower_bound(all(a), v))
#define UB(a, v)            (upper_bound(all(a), v))

/**----------------------Graph Moves----------------*/
const int  fx[] =   {+1, -1, +0, +0};                      // 4 X directions
const int  fy[] =   {+0, +0, +1, -1};                      // 4 Y directions
const int fx8[] =   {+0, +0, +1, -1, -1, +1, -1, +1};      // King X Moves
const int fy8[] =   {-1, +1, +0, +0, +1, +1, -1, -1};      // King Y Moves
const int  kx[] =   {-2, -2, -1, -1,  1,  1,  2,  2};      // Knight X Moves
const int  ky[] =   {-1,  1, -2,  2, -2,  2, -1,  1};      // Knight Y Moves
/*------------------------------------------------*/

/**-----------------------Bitmask------------------*/
int  Set    (int N,int pos) {return N=N | (1<<pos);}    /// turn a bit on
int  reset  (int N,int pos) {return N= N & ~(1<<pos);}  /// turn a bit off
bool check  (int N,int pos) {return (bool)(N & (1<<pos));} /// check, if a bit is on or not
/*------------------------------------------------*/

const db  PI  = acos(-1.0);
const db  eps = 1e-9;
const int mod = 1e9 + 7;
const int mx  = 2*mx5;

int n;
int a[mx3], b[mx3];

int dp[mx3][mx4];
int fun(int i, int h){
    if(h <= 0) return 0;
    if(i == n) return INF;
    if(dp[i][h] != -1)
        return dp[i][h];
    int ans = INF;
    ans = min(ans, b[i]+fun(i, h-a[i]));
    ans = min(ans, fun(i+1, h));
    return dp[i][h] = ans;
}

int main(){FasterIO;
    #ifndef ONLINE_JUDGE
//        inOut;
    #endif

    int h;
    cin >> h >> n;
    for(int i=0; i<n; i++)
        cin >> a[i] >> b[i];

    mem(dp, -1);
    cout << fun(0, h) nl;

    return 0;
}


Measured memory_bytes: 39936