#include                            <iostream>
#include							<list>
#include                            <stdio.h>
#include                            <math.h>
#include                            <string.h>
#include                            <time.h>
#include                            <stdlib.h>
#include                            <string>
#include                            <bitset>
#include                            <vector>
#include                            <set>
#include                            <map>
#include                            <queue>
#include                            <algorithm>
#include                            <sstream>
#include                            <stack>
#include                            <iomanip>
#include                            <numeric>
#include							<unordered_map>
using namespace                     std;
#define int                         int64_t
#define baba_shiv                   ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mpii                        map<int,int>
#define pb                          push_back
#define mkp                         make_pair
#define all(x)                      x.begin(),x.end()
#define allr(x)                     x.rbegin(),x.rend()
#define ub(v,x)                     upper_bound(all(v),x)
#define lb(v,x)                     lower_bound(all(v),x)
#define bs(v,x)                     binary_search(all(v),x)
#define gcd(a,b)                    __gcd(a,b)
#define lcm(a,b)                    (a*b)/__gcd(a,b)
#define vi                          vector<int>
#define pii                         pair<int,int>
#define vpii                        vector<pii>
#define vs                          vector<string>
#define ff                          first
#define ss                          second
#define MOD                         1000000007
#define double						long double
/***********************************************************************************************************************/
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	typename vector< T > :: const_iterator it;
	for ( it = v.begin(); it != v.end(); it++ ) {
		if ( it != v.begin() ) os << ", ";
		os << *it;
	}
	return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	typename set< T > :: const_iterator it;
	for ( it = v.begin(); it != v.end(); it++ ) {
		if ( it != v.begin() ) os << ", ";
		os << *it;
	}
	return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	typename map< F , S >::const_iterator it;
	for ( it = v.begin(); it != v.end(); it++ ) {
		if ( it != v.begin() ) os << ", ";
		os << it -> first << " = " << it -> second ;
	}
	return os << "]";
}

#define deb(x) cerr<< #x << " = " << x << endl;

/***********************************************************************************************************************/
bool compare(pii &a, pii &b)
{
	return (1.0 * (a.ff) / a.ss) < (1.0 * (b.ff) / b.ss);
}
signed main()
{
	baba_shiv;
	int h, n;
	cin >> h >> n;
	vpii vec;
	vec.resize(n);
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		vec.pb({x, y});
	}
	//deb(vec.size());
	vector<int> dp(1e5, 1e18);
	dp[0] = 0;//where dp array represents minimum coins required to the monster H
	for (int i = 0; i <=h; i++)
	{
		for (int j = 0; j < vec.size(); j++)
		{
			if (i >= vec[j].ff)
			{
				dp[i] = min((dp[i - vec[j].ff] + vec[j].ss), dp[i]);
			}
			else
			{
				dp[i] = min(dp[i], dp[0] + vec[j].ss);
			}
		}
	}
	//deb(dp);
	cout << dp[h];


}



Measured memory_bytes: 1152