/*
  "Piece of shit. Stupid piece of shit. I'm a real stupid piece
   of shit. But I know I'm a piece of shit. That at least makes
   me better than all the pieces of shit that don't know they're
   pieces of shit. Or is it worse?"
     - BoJack F. Horseman
*/
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstring>
#include<climits>
#include<numeric>
#include<random>
#include<fstream>
#include<chrono>

#include<deque>
#include<queue>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<unordered_map>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define int          long long
#define ld           long double
#define pii          pair<int,int>
#define vi           vector<int>
#define maxpq        priority_queue<int>
#define minpq        priority_queue<int,vi,greater<int>>
#define pb           push_back
#define mp           make_pair
#define ff           first
#define ss           second
#define endl         '\n'
#define rep(i,s,e)   for(int i=s;i<=e;i++)
#define brep(i,s,e)  for(int i=s;i>=e;i--)
#define all(x)       (x).begin(),(x).end()
#define ball(x)      (x).rbegin(),(x).rend()
#define sz(x)        (int)x.size()
#define mem(x,y)     memset(x,y,sizeof(x))
#define milf(x)      x.reserve(1LL<<14LL); x.max_load_factor(0.25);
#define pbds         tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define VR46         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
mt19937              rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9+7;
ld EPS = 1e-12;
const int INF32 = 0x3F3F3F3F;
const int INF = 0x3F3F3F3F3F3F3F3F;
const int crng = rng();

// const int N = 2e7;
// int a[N];

const int N = 1e3 + 5;
const int H = 2e4;
int dp[H];

signed main()
{
    VR46 ifstream fin("input.txt"); ofstream fout("output.txt");
    // auto start = chrono::high_resolution_clock::now();

    // GANDU TEST CASE BNAKE TEST KRLE; CHECK BOUNDS;
    // int t; cin>>t; rep(test,1,t)
    {
        int h, n;
        cin>>h>>n;
        vector<pii> a(n);
        for(auto &i:a) cin>>i.ff>>i.ss;
        mem( dp,INF );

        dp[0] = 0;
        rep(i,0,n-1)
        {
            rep(j,0,H-1)
            {
                if( j+a[i].ff >=H ) break;
                dp[ j+a[i].ff ] = min( dp[ j+a[i].ff ],dp[j]+a[i].ss );
            }
        }

        // rep(i,0,2*h) cout<<dp[i]<<" ";
        // cout<<endl;
        int ans = INF;
        rep(i,h,H-1) ans = min( ans,dp[i] );
        cout<<ans<<endl;
        // dp[0][0] = 0, dp[0][ a[0].ff ] = a[0].ss;
        // rep(i,1,n-1)
        // {

        // }
    }

    // auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout<<"Time taken by function: "<<duration.count()<<" milliseconds"<<endl;

    // *( hsh.find_by_order(k) ) kth smallest, from 0
    // hsh.order_of_key(k) num of ele str less than k
    // change less to less_equal for multiset pbds
    // Create struct HASH; Use milf(x) for every hashmap; Use CRNG xor;
}

Measured memory_bytes: 384