using namespace std;

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

#define getBit(x,i) (x&(1<<i))
#define setBit(x,i) (x|(1<<i))
#define mem(A,N) memset(A,N,sizeof(A))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define rep(i, x, y)  for(int i = x; i < y; ++i)
#define Rep(i, x, y)  for(int i = x; i <= y; ++i)
#define srep(i, x, y) for(int i = x; i > y; --i)
#define sRep(i, x, y) for(int i = x; i >= y; --i)
#define All(v) v.begin(),v.end()
#define sortA(a) sort(a, a+n)
#define sortArr(a, i, n) sort(a+i, a+n)
#define SortArr(a, i, n) sort(a+i, a+n+1)
#define Sort(x) sort(x.begin(), x.end())
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define fi first
#define se second
#define concatenate(a, b) std::copy(b.begin(), b.end(), std::back_inserter(a));
#define fcout(x) cout << fixed << setprecision(x)
#define ifcout(x, a, b) if(x) cout << a << '\n'; else cout << b << '\n'
#define makeUnique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define inRange(a01, b02, c03) (a01 <= b02 && b02 < c03)
#define min3(a01, b02, c03) (min(min(a01, b02), c03))
#define max3(a01, b02, c03) (max(max(a01, b02), c03))

static constexpr int inf = 1'000'000'001;
static constexpr int ninf = -1'000'000'001;
static constexpr long long llInf = 2'000'000'000'000'000'001LL;
static constexpr long long nllInf = -2'000'000'000'000'000'001LL;

static constexpr double Pi = 3.14159265358979323846;
static constexpr double eps = 1e-9;
static constexpr int mod = 1000000007;
static constexpr int mod2 = 1000000006;

#define Debug_Enabled
#ifdef Debug_Enabled
#define dump(x) cout << #x << " = " << (x) << endl;
#define dump2(x1, x2) cout << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << endl;
#define dump3(x1, x2, x3) cout << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << ", " << #x3 << " = " << x3 << endl;
#define dump4(x1, x2, x3, x4) cout << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << ", " << #x3 << " = " << x3 << ", " << #x4 << " = " << x4 << endl;
#define write(x) cout << #x << " = " << (x) << ", ";

#define edump(x) cerr << #x << " = " << (x) << endl;
#define edump2(x1, x2) cerr << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << endl;
#define edump3(x1, x2, x3) cerr << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << ", " << #x3 << " = " << x3 << endl;
#define edump4(x1, x2, x3, x4) cerr << #x1 << " = " << x1 << ", " << #x2 << " = " << x2 << ", " << #x3 << " = " << x3 << ", " << #x4 << " = " << x4 << endl;
#define ewrite(x) cerr << #x << " = " << (x) << ", ";

#define printSet(s) for(auto itera_tor = s.begin(); itera_tor!=s.end(); itera_tor++) (itera_tor==s.begin())? cout << *itera_tor : cout << ' ' << *itera_tor; cout << endl;
#define printMap(m) for(auto itera_tor = m.begin(); itera_tor!=m.end(); itera_tor++) (itera_tor==m.begin())? cout << '(' << itera_tor->first << ", " << itera_tor->second << ')' \
																						: cout << " (" << itera_tor->first << ", " << itera_tor->second << ')'; cout << endl;
#define printPairSet(s) for(auto itera_tor = s.begin(); itera_tor!=s.end(); itera_tor++) (itera_tor==s.begin())? cout << '(' << itera_tor->first << ", " << itera_tor->second << ')' \
																						: cout << " (" << itera_tor->first << ", " << itera_tor->second << ')'; cout << endl;
#define printPairMap(m) for(auto itera_tor = m.begin(); itera_tor!=m.end(); itera_tor++) (itera_tor==m.begin())? cout << '(' << itera_tor->first.first << ", " << itera_tor->first.second << ": " \
															<< itera_tor->second << ')' : cout << " (" << itera_tor->first.first << ", " << itera_tor->first.second << ": " << itera_tor->second << ')'; cout << endl;

#define coutVector(x) for(auto itera_tor = x.begin(); itera_tor!=x.end(); itera_tor++) (itera_tor==x.begin())? cout << *itera_tor : cout << ' ' << *itera_tor;
#define printVector(x) for(auto itera_tor = x.begin(); itera_tor!=x.end(); itera_tor++) (itera_tor==x.begin())? cout << *itera_tor : cout << ' ' << *itera_tor; cout << endl;
#define commaVector(x) for(auto itera_tor = x.begin(); itera_tor!=x.end(); itera_tor++) (itera_tor==x.begin())? cout << *itera_tor : cout << ' ' << *itera_tor; cout << ", ";
#define printArray(a,x,y) for(auto itera_tor = a+x; itera_tor != a+y; itera_tor++) (itera_tor==a+x)? cout << *itera_tor : cout << ' ' << *itera_tor; cout << endl;
#define PrintArray(a,x,y) for(auto itera_tor = a+x; itera_tor != a+y+1; itera_tor++) (itera_tor==a+x)? cout << *itera_tor : cout << ' ' << *itera_tor; cout << endl;

#else

#define dump(x)
#define dump2(x1, x2)
#define dump3(x1, x2, x3)
#define dump4(x1, x2, x3, x4)
#define write(x)

#define edump(x)
#define edump2(x1, x2)
#define edump3(x1, x2, x3)
#define edump4(x1, x2, x3, x4)
#define ewrite(x)

#define printSet(s)
#define printMap(m)
#define printPairSet(s)
#define printPairMap(s)
#define writeVector(x)

#define countVector(x)
#define printVector(x)
#define commaVector(x)
#define printArray(a,x,y)
#define PrintArray(a,x,y)

#endif

// ***************** End Of Template ********************

int dp[1001][10001];
int a[1000];
int b[1000];
int h, n;

int f(int i, int k) {
	if(dp[i][k] != -1) return dp[i][k];
	
	if(k == 0) return dp[i][k] = 0;
	if(i == n) return dp[i][k] = 1000'000'001;
	
	return dp[i][k] = min(f(i + 1, k), b[i] + f(i, k - min(k, a[i])));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> h >> n;
	rep(i, 0, n) { cin >> a[i] >> b[i]; }
	memset(dp, -1, sizeof(dp));
	cout << f(0, h);
	return 0;
}

Measured memory_bytes: 39936