/*
    NO 
        TIME 
            TO 
                DIE
                    --007
                            */
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
//#include <boost/functional/hash.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int lli;
lli mod=1e9+7ll;
lli INF=1e17;
lli eps=1e-8;
#define sqr(x) (x) * (x)
#define bip(n) __builtin_popcountll(n)//no of ones bit in binary!!
#define bictz(n) __builtin_ctzll(n)//no of trailing zeroes in binary!!
#define biclz(n) __builtin_clzll(n)//no of leading zeroes in binary!!
#define bffs(n) __builtin_ffsll(n)//index of first one bit!!
typedef pair<lli,lli> ll;
#define mem1(a,x) fill(&a[0], &a[0] + sizeof(a) / sizeof(a[0]), x)
#define mem2(a,x) fill(&a[0][0], &a[0][0] +sizeof(a)/sizeof(a[0][0]),x)
#define mem3(a,x) fill(&a[0][0][0], &a[0][0][0] +sizeof(a)/sizeof(a[0][0][0]),x)
#define fi1 ifstream fin("input.txt")
#define of1 ofstream fout("output.txt")
int fmx(int x, int y) { return (((y-x)>>(31))&(x^y))^y; }
int fmi(int x, int y) { return (((y-x)>>(31))&(x^y))^x; }
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;
lli n,q,z,y,k,x,c;
const double pi=3.14159265358979323846;
lli add(lli a, lli b) {
 	lli res = a + b;
 
 	while (res >= mod) res -= mod;
 
 	while (res < 0) res += mod;
 
 	return res;
}
// Thi
//matrix exponentiation is associative and distributive
lli me(lli a,lli b)
{
    lli res=1;
    while(b)
    {
        if(b&1)
        res=(res%mod*a%mod)%mod;
        a=a*a;
        a%=mod;
        b=b>>1;
    }
    return res;
}
lli mI(lli a)
{
    return (me(a,mod-2)%mod+mod)%mod;
}
bool cmp(ll a,ll b)
{
    if(a.second==b.second)
    return a.first<b.first;
    return a.second<b.second;
}
struct pt
{
    long double x,y;
    pt() {}
    pt(long double _x, long double _y) : x(_x), y(_y) {}
    pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); }
    long double dot(const pt& p) const { return x * p.x + y * p.y ; }
    long double cross(const pt& p) const { return x * p.y - p.x * y; }
};
 
bool operator < (pt p, pt q)
{
 if(p.x!=q.x)
 return p.x<q.x;
 return p.y<q.y;
}
 
struct seg
{
    pt p,q;
};
 
double get_distance(pt p,pt q)
{
    return sqrt(pow(p.x-q.x,2.0) + pow(p.y-q.y,2.0) );
}
 
double get_area(pt p1,pt p2,pt p3)
{
    return (p2.x - p1.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p2.y - p1.y);
}
 
double get_area(long double r)
{
    return pi*(r*r);
}
 
bool equall_to(pt p , pt q)
{
    if(p.x==q.x&&p.y==q.y)
    return true;
    return false;
}
struct edge
{
    double x,y,z;
};
 
bool operator <(edge e,edge f)
{
    return e.x<f.x;
}
lli dp[1005][20005];
int main()
{
 ios_base::sync_with_stdio(0);
 lli h,n;
 cin>>h>>n;
 ll p[n+1];
 for(int i=1;i<=n;i++)
 cin>>p[i].first>>p[i].second;
 
 mem2(dp,1e15);
 lli ans=1e15;
 for(int i=1;i<=n;i++)
 {
     dp[i][0]=0;
 }
//  dp[1][0]=0;
 for(int i=1;i<=n;i++)
 {
     for(int j=0;j<=20004;j++)
     {
         if(j-p[i].first<0)
         {
             dp[i][j]=min(dp[i][j],dp[i-1][j]);
         }
         else
         {
            dp[i][j]=min(dp[i][j],dp[i][j-p[i].first]+p[i].second);
             dp[i][j]=min(dp[i][j],dp[i-1][j-p[i].first]+p[i].second);
             dp[i][j]=min(dp[i][j],dp[i-1][j]);
         }
     }
    //  ans=min(ans,dp[i][h]);
 }
 for(int i=h;i<=20000;i++)
 ans=min(ans,dp[n][i]);
 cout<<ans;
}

Measured memory_bytes: 157440