/*****/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);
#include <stdexcept>

//#define int long long

using namespace std;
using ll = long long;
using ld = long double;
using vecint = vector<int>;
using vecll = vector<long long>;
using pll = pair<long, long>;
template<class T> using pr = pair<T, T>;
template<class T> using vec = vector<T>;

#ifdef _MSC_VER
#define scanf scanf_s
#endif // _MSC_VER

#define nextline() (std::cerr << "\n")
#define debug(x) (std::cerr << (x) << "\n")
#define debug_tab(n, x) (std::cerr << strMulti("\t",n) << (x) << "\n")
#define debug_cout(x) (std::cerr << #x << " : " <<  (x) << "\n")
#define debug_tabcout(n, x) (std::cerr << strMulti("\t",n) << #x << " : " <<  (x) << "\n")
#define debug_headcout(h, x) (std::cerr << h << " : " <<  (x) << "\n")
#define debug_tabheadcout(n, h, x) (std::cerr << strMulti("\t",n) << h << " : " <<  (x) << "\n")

#define rep(i, n) for(ll i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(ll i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(ll i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(ll i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair(a, b)
constexpr int INF = 2000000100;
constexpr ll MOD = 1000000007;	// 10e9+7
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline T divup(T a, T b) { if (a % b == 0) { return a / b; } return a / b + 1; }
std::string strMulti(std::string t, int n) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; }
template<class T> T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; }
template<class T> T math_C(T m, T n) { T ret = mathP(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; }
template<class T> bool compare_by_b(pair<T, T> a, pair<T, T> b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; }
//template<class T> T math_gcd(T a, T b) { a = abs(a); b = abs(b); if (a < b) { std::swap(a, b); } T tmp; while (b != 0) { tmp = b; b = a % b; a = tmp; } return a; }
//template<class T> T math_lcm(T a, T b) { a = abs(a); b = abs(b); if (a > b) { std::swap(a, b); } if (a == 1) { return b; } T i = a; while (i % b != 0) { i += a; } return i; }
template<class T> T mod_pow(T x, T n, const T& p) { T ret = 1; while (n > 0) { if (n & 1) { (ret *= x) %= p; } (x *= x) %= p; n >>= 1; } return ret; }
//inline void cinvecll(vecll& const A, ll const N) { vecll::iterator itr = A.begin(); for (int i = 0; i < N; i++) { scanf("%lld", &*itr); itr++; } }

//ll gcd(ll x, ll y) { return (x % y) ? gcd(y, x % y) : y; }
//ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

/*****/

#define max(a, b) ((a) > (b) ? a : b)

void Main()
{
	ll H, N;
	cin >> H >> N;
	vec<pll> M(N);
	rep(i, N)	cin >> M[i].first >> M[i].second;

	vecll dp(H + 1, INF);
	dp[H] = 0;

	rrep(i, H + 1)
	{
		rep(j, N)
		{
			chmin(dp[max(0, i - M[j].first)], dp[i] + M[j].second);
		}
	}

	/*
	rrep(i, H + 1)
	{
		debug_cout(i);
		debug_tabcout(1, dp[i]);
	}
	//*/

	cout << dp[0];
}

/*****/

int main()
{
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);

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



	/*
	while (true)
	{
		Main();
		cout << endl;
	}
	//*/


	Main();

	return 0;
}


Measured memory_bytes: 384