#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll                 long long
#define LL                 long long
#define ull                unsigned long long
#define pii                pair<int, int>
#define pll                pair<ll, ll>
#define pil                pair<int, ll>
#define pli                pair<ll, int>
#define vi                 vector<int>
#define vl                 vector<ll>
#define vii                vector<pii>
#define vll                vector<pll>
#define vil                vector<pil>
#define vli                vector<pli>
#define vvi                vector<vi>
#define vvl                vector<vl>
#define pb                 push_back
#define mp                 make_pair
#define ff                 first
#define ss                 second
#define sz(x)              (int)x.size()
#define all(v)             v.begin(), v.end()
#define rall(v)            v.rbegin(), v.rend()
#define fill(a, b)         memset(a, b, sizeof(a))
#define endl               '\n'
#define policy_set         tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define policy_multiset    tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

template <typename T> T gcd(T a, T b) {return !b ? a : gcd(b, a % b);}
template <typename T> T lcm(T a, T b) {return a * (b / gcd(a, b));}
template <typename T> inline void smin(T &a, T b) {a = a < b ? a : b;}
template <typename T> inline void smax(T &a, T b) {a = a > b ? a : b;}

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ", ";
	err(++it, args...);
}

template <typename T> inline void Int(T &n) {
	n = 0; int f = 1; register int ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
	n = n * f;
}

template <typename T, typename TT> inline void Int(T &n, TT &m) { Int(n); Int(m); }
template <typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) { Int(n, m); Int(l); }
template <typename T, typename TT, typename TTT, typename TTTT> inline void Int(T &n, TT &m, TTT &l, TTTT &k) { Int(n, m); Int(l, k); }
template <typename T, typename TT, typename TTT, typename TTTT, typename TTTTT> inline void Int(T &n, TT &m, TTT &l, TTTT &k, TTTTT &x) { Int(n, m, l); Int(k, x); }

const int mod = (int) 1e9 + 7;
const ll  Mod = (ll) 1e9 + 7;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll) a * b % mod;}

const int inf = (int) 2e9 + 5;
const ll  Inf = (ll) 2e18 + 5;
const int N   = (int) 2e3 + 5;

ll n, m;


int dp[N][N][2];

int call(int pos, int num, int equal) {
    if(pos == n) return 1;
    int& ans = dp[pos][num][equal];
    if(~ans) return ans;
    ans = 0;
    for(int i = 1; i <= m; i++) {
    	if(equal && i == num) continue;
    	ans = add(ans, call(pos + 1, i, num == i));
    }
    return ans;
}

int bigmod(ll a, ll b) {
	if (!b) return 1;
	int x = bigmod(a, b / 2);
	x = mul(x, x);
	if (b % 2) x = mul(x, (int)(a % mod));
	return x;
}


int solve() {
	int h, n; Int(h, n);
	vi a(n), b(n);
	for(int i = 0; i < n; i++) {
        Int(a[i], b[i]); 
	}
	vi dp(3e4 + 5, inf);
	dp[0] = 0;
	for(int i = 1; i < 3e4; i++) {
		for(int j = 0; j < n; j++) {
            if(i - a[j] >= 0) {
            	dp[i] = min(dp[i], dp[i - a[j]] + b[j]);
            }
		}
	}
	int ans = inf;
	for(int i = h; i < 3e4; i++) {
		smin(ans, dp[i]);
	}
	printf("%d\n", ans);
	return 0;
}

int main() {
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	int test = 1, tc = 0;
	//Int(test);
	//cin >> test;
	while (test--) {
		//printf("Case %d: ", ++tc);
		solve();
	}
	return 0;
}

Measured memory_bytes: 384