// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'



//↓0-originか1-originでn回繰り返し

#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   //0-indexed昇順

#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) //1-indexed昇順

#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-indexed降順

#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-indexed降順

#define all(x) (x).begin(),(x).end()



typedef long long ll;

typedef long double ld;

typedef vector<int> vi;

typedef vector<vi> vii; //2次元配列

typedef vector<ll> vll;

typedef pair<int, int> PII;



template<typename T>

using vec = vector<T>;

template<class T>

using maxheap = std::priority_queue<T>;

template<class T>

using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;



template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}

template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}



const ld PI = acos(-1.0L);

const ll infll = (1LL<<62)-1;

const int inf = (1<<30)-1;

const int mod = 1000000007;

//const int mod = 998244353;





/*FUNCs=================================================*/





/*MAIN==================================================*/

signed main(){

    cin.tie(nullptr);

    ios::sync_with_stdio(false);   //cin cout 高速化

    //cout << fixed << setprecision(10);



    vi dp(112345, inf);

    int h,n,maxi; cin >> h >> n;

    vi a(n), b(n);

    rep(i,n) {

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

        chmax(maxi, a[i]);

    }



    dp[0] = 0;

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

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

            if(112345 < i+a[j]) continue;

            dp[i+a[j]] = min(dp[i+a[j]], dp[i] + b[j]);

        }

    }

    int ans = inf;

    for(int i = h; i <= h + maxi; ++i) {

        chmin(ans, dp[i]);

    }

    cout << ans << '\n';

    //for(int i = 0; i < 11; i++) debug(dp[i]);

}

// Faster C++ solution for the same problem (measured speedup: 1.2452818819756541x):
#include <bits/stdc++.h>



#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up

#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up

#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down

#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down

#define all(x) (x).begin(),(x).end()



using namespace std;



template<typename T>

using vec = vector<T>;

using i32 = int_fast32_t;

using i64 = int_fast64_t;

using u32 = uint_fast32_t;

using u64 = uint_fast64_t;

using ll = long long;

using ld = long double;

using vi = vec<int_fast32_t>;

using vl = vec<int_fast64_t>;

using vld = vec<ld>;

using vii = vec<vi>;

using PII = pair<int_fast32_t, int_fast32_t>;



template<class T>

using maxheap = std::priority_queue<T>;

template<class T>

using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;



template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}

template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}



const ld Pi = std::acos(-1.0L);

constexpr ll infll = (1LL<<62)-1;

constexpr int inf = (1<<30)-1;

const int mod = 1000000007;

// const int mod = 998244353;





/*FUNCs=================================================*/





/*MAIN==================================================*/

signed main(){

    int START_TIME = clock();

    cin.tie(nullptr);

    ios::sync_with_stdio(false);

//    cout << fixed << setprecision(15);



    i32 h, n; cin>> h >> n;

    vi a(n), b(n);

    rep(i,n) cin >> a[i] >> b[i];



    vi dp(h+1, inf);  // cost  mons_HP

    dp[h] = 0;

    for(i32 i = h; i >= 0; --i) {

        rep(j,n) {

            chmin(dp[max<i32>(0,i-a[j])], dp[i] + b[j]);

        }

    }



    cout << dp[0] << '\n';



    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));

}