#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <ctime>
#include <map>
#include <set>
#include <unordered_set>

using namespace std;

#define endl "\n"
#define age first
#define pos second
#define Z third
#define mp make_pair
#define mt make_triple

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ld PI = 3.141592653589793;
const ld E = 2.71828182845904523;
const ll LLINF = 4000000009000000099;
const ll INF = 1009000099;
const ll MOD7 = 1000000007;
const ll MOD9 = 1000000009;

template<class A, class B, class C> struct triple { A first; B second; C third; triple(A, B, C); triple(); };
template<class A, class B, class C> triple<A, B, C>::triple(A a, B b, C c) { first = a; second = b; third = c; }
template<class A, class B, class C> triple<A, B, C>::triple() { }
template<class A, class B, class C> triple<A, B, C> make_triple(A a, B b, C c) { triple<A, B, C> t(a, b, c); return t; }
template<class A, class B, class C> bool operator<(triple<A, B, C> a, triple<A, B, C> b) { if (a.first != b.first) return a.first < b.first; if (a.second != b.second) return a.second < b.second; if (a.third != b.third) return a.third < b.third; }
template<class T> T inline sqr(T a) { return a * a; }

const ll SZ = 2;

typedef vector<vector<ll>> Matrix;

#define C_MATRIX vector<vector<ll>> m(SZ, vector<ll>(SZ));

Matrix mul(const Matrix& a, const Matrix& b, ll mod)
{
	C_MATRIX;
	for (int i = 0; i < SZ; ++i)
		for (int j = 0; j < SZ; ++j)
			for (int k = 0; k < SZ; ++k)
			{
				m[i][j] += a[i][k] * b[k][j];
				m[i][j] %= mod;
			}
	return m;
}

inline Matrix bpow(const Matrix& matrix, ll d, ll mod)
{
	Matrix res = { {1, 0}, {0, 1} };
	Matrix p = matrix;
	while (d != 0)
	{
		if (d & 1)
			res = mul(res, p, mod);
		p = mul(p, p, mod);
		d >>= 1;
	}

	return res;
}

inline ll bpow(ll a, ll d, ll mod)
{
	ll res = 1, p = a;
	while (d != 0)
	{
		if (d & 1)
		{
			res *= p;
			res %= mod;
		}
		p = (p * p) % mod;
		d >>= 1;
	}

	return res;
}
ll bpow(ll a, ll d) { if (d == 0) return 1; ll t = bpow(a, d / 2); t = (t * t); if (d & 1) t = (t * a); return t; }
ll gcd(ll a, ll b) { while (a && b) if (a > b) a %= b; else b %= a; return a + b; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll C(ll n, ll k) { ll res = 1; for (int i = 1; i <= k; ++i) res = res * (n - k + i) / i; return res; }
inline ll C(ll n, ll k, ll mod) { ll u = 1, d = 1; for (int i = 2; i <= n; ++i) u = (u * i) % mod; int x = max(k, n - k), z = min(k, n - k); for (int i = 2; i <= x; ++i) { d = (d * i) % mod; if (i <= z) d = (d * i) % mod; } d = bpow(d, mod - 2, mod); ll res = (u * d) % mod; return res; }

using namespace std;

void solve1()
{
	int n; cin >> n;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].first;
		v[i].second = i;
	}
	sort(v.begin(), v.end());

	vector<set<int>> cycles;
	set<int> used;
	for (int i = 0; i < n; ++i)
	{
		set<int> s;
		int idx = i;
		while (used.find(v[idx].first) == used.end())
		{
			used.insert(v[idx].first);
			s.insert(v[idx].first);
			idx = v[idx].second;
		}

		if (s.size() > 1)
			cycles.push_back(s);
	}
	int res = 0, glMin = v.front().first;
	for (auto cycle : cycles)
	{
		int sum = 0, locMin = *cycle.begin();
		for (auto it = cycle.begin(); it != cycle.end(); ++it)
			sum += *it;
		res += min(sum + locMin * (cycle.size() - 2),
			sum + locMin + glMin * (cycle.size() + 1));
	}

	cout << res << endl;
}

ll f(ll n)
{
	if (n == 1) return 1;
	else return 2 * f(n / 2) + 1;
}

void solve()
{
	int h, n; cin >> h >> n;
	vector<int> d(n);
	vector<int> m(n);
	int sh = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> d[i] >> m[i];
		sh = max(sh, d[i]);
	}

	vector<int> dp(h + sh + 1, INF);
	dp[0] = 0;
	for (int i = 1; i <= h + sh; ++i)
		for (int j = 0; j < n; ++j)
			if (i - d[j] >= 0)
				dp[i] = min(dp[i], dp[i - d[j]] + m[j]);

	int res = INF;
	for (int i = h; i < h + sh + 1; ++i)
		res = min(res, dp[i]);
	cout << res;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
	solve();
	return 0;
}


Measured memory_bytes: 384