/*
	Template from @50m_regent
	https://note.mu/50m_regent/n/na84b255e8679
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INIT cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);


/* コンテナ基本 */

// コンテナの最初と最後のイテレータ
#define all(x) (x).begin(), (x).end()
// 昇順ソート
#define asc(v) sort(all(v))
// 降順ソート
#define desc(v) sort(all(v), greater<ll>())


/* カウント系 */

// vの中にあるcの個数を数える
#define ct(v, c) count(all(v), c)
// vの中でc未満の要素の個数を数える
#define lh(v, c) lower_bound((v).begin(), (v).end(), c) - (v).begin()
// vの中でcより大きい要素の個数を数える
#define uh(v, c) upper_bound((v).begin(), (v).end(), c) - (v).end()
// vの中でc以下の要素の個数を数える
#define lm(v, c) upper_bound((v).begin(), (v).end(), c) - (v).begin()
// vの中でc以上の要素の個数を数える
#define um(v, c) lower_bound((v).begin(), (v).end(), c) - (v).end()


/* ループ系 */

#define _overload(_1, _2, _3, name, ...) name
// iをaからb-1まで+1しながら繰り返す(b-a回繰り返す)
#define repi(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++)
// iを0からn-1まで+1しながら繰り返す(n回繰り返す)
#define _rep(i, n) repi(i, 0, n)
// 
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
// iをa-1からbまで-1しながら繰り返す(a-b回繰り返す)
#define revi(i, a, b) for(ll i = (ll)(a) - 1; i >= (ll)(b); i--)
// iをnから0まで-1しながら繰り返す(n回繰り返す)
#define _rev(i, n) revi(i, n, 0)
// 
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
// vのそれぞれの要素に対して繰り返す
#define each(a, v) for(auto&& a: v)


/* 入力系 */

// 標準入力から何も受け取らない
void in(){}
// 標準入力から複数の値を受け取る
template<typename F, typename... R>
bool in(F& f, R&... r){
	if(cin >> f){
		in(r...);
		return true;
	}else{
		return false;
	}
}
// 標準入力からコンテナvに値を受け取る
#define inv(v) each(i, v) in(i)


/* 出力系 */

// 標準出力
#define out(x) cout << (x)
// 半角スペースを標準出力
#define space() cout << " "
// 改行を標準出力
#define indent() cout << '\n'
// 複数の値を標準出力
void print(){}
template<typename F, typename... R> void print(F f, R... r){out(f), indent(), print(r...);}
// コンテナの値を全て標準出力
#define printv(v) each(i, v) out(i), space(); indent()
// デバッグ用のヘッダをエラー出力
#define debughead(x) cerr << "Line " << __LINE__ << ": " << #x << ": "
// デバッグ用の値をエラー出力
#define debugout(x) cerr << (x) << " "
// デバッグ用の改行をエラー出力
#define debugindent() cerr << '\n'
// デバッグ出力
#define debug(x) debughead(x), debugout(x), debugindent()
// YES or NO を標準出力
#define YN(x) out((x) ? "YES" : "NO"), indent()
// Yes or No を標準出力
#define Yn(x) out((x) ? "Yes" : "No"), indent()
// yes or no を標準出力
#define yn(x) out((x) ? "yes" : "no"), indent()


/* 定数 */

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll LIMIT = 100001;
const ll S_LIMIT = 101;
const ld EPS = 1e-15;
const ld PI = acos(-1);
const ll dx[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const ll dy[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";


/* 基本アルゴリズム */

// 最大公約数
#define gcd __gcd
// 最小公倍数
ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
// ワーシャルフロイド用配列
ll g[S_LIMIT][S_LIMIT] = {};
// DP用配列
// ll dp[LIMIT][LIMIT] = {};
// MOD対応累乗
ll modpow(ll x, ll n){ return n < 2 ? x : modpow(x * x, n / 2) * (n % 2 ? x : 1) % MOD; }
// MOD対応階乗
ll modfact(ll n){ return n < 2 ? 1 : modfact(n - 1) * n % MOD; }
// MOD対応コンビネーション
ll modcomb(ll n, ll r){ return modfact(n) * modpow(modfact(r), MOD - 2) % MOD * modpow(modfact(n - r), MOD - 2) % MOD; }
// aをmax(a,b)にする
template<typename T> bool chmax(T& a, T b){return (a = max(a, b)) == b;}
// aをmin(a,b)にする
template<typename T> bool chmin(T& a, T b){return (a = min(a, b)) == b;}
// 階乗
ll factorial(ll a){return a < 2 ? 1 : factorial(a - 1) * a;}
// 1～aの総和
ll summation(ll a){return a < 1 ? 0 : (a * a + a) / 2;}
// コンビネーション
ll combination(ll n, ll r){
	ll res = 1;
	rep(i, 1, r + 1){
		res *= n--, res /= i;
	}
	return res;
}
// 素数判定
bool isPrime(ll n){
	rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		if(!(n % i)){
			return false;
		}
	}
	return true;
}
// ワーシャルフロイド
void warshall(int n){
	rep(i, n){
		rep(j, n){
			rep(k, n){
				chmin(g[j][k], g[j][i] + g[i][k]);
			}
		}
	}
}
// 約数列挙
vector<int> divisor(int n){
	vector<int> ans;
	rep(i, 1, sqrt(n) + 1){
		if(!(n % i)){
			ans.push_back(i);
			if(i * i < n){
				ans.push_back(n / i);
			}
		}
	}
	return ans;
}
// 素因数分解
map<int, int> factorization(int n){
	map<int, int> ans;
	rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		while(!(n%i)){
			ans[i]++, n /= i;
		}
	}
	if(n > 1){
		ans[n]++;
	}
	return ans;
}
// Union-Find
struct UF{
	vector<int> t;
	UF(int size): t(size, -1){}
	int root(int x){ return t[x] < 0 ? x : t[x] = root(t[x]); }
	int size(int x){ return -t[root(x)]; }
	bool isSame(int x, int y){ return root(x) == root(y); }
	bool unite(int x, int y){
		x = root(x), y = root(y);
		if(x != y){
			if(t[y] < t[x]){
				swap(x, y)
			;}
			t[x] += t[y], t[y] = x;
		}
		return x != y;
	}
};

ll H, N = 0;
string s, t;

int main(){
	INIT;
	in(H, N);
	vector<pair<int, int>> magic(N);
	each(a, magic) in(a.first, a.second);
	
	// dp[N]: 体力をN削るのに必要な最小MP
	int dp[10010];
	dp[0] = 0;
	
	rep(i, 0, H+1) {
		int minMP = INT_MAX;
		each(a, magic) {
			// dp[i - a.first] + a.second : dp[i]を削るのに使用するMP
			int c = (i < a.first) ? 0 : a.first;
			chmin(minMP, dp[i - c] + a.second);
		}
		dp[i] = (minMP == INT_MAX) ? dp[i-1] : minMP;
		// printf("dp[%lld] %d\n", i, dp[i]);
	}
	
	print(dp[H-1]);
	return 0;
}


Measured memory_bytes: 256