#include<bits/stdc++.h>
    using namespace std;


    #define mp make_pair
    #define ll  int
    #define f(i,n) for(ll i=0;i<n;i++)
    #define ff(i,n) for(ll i=1;i<=n;i++)
    #define  pb push_back
    //#define a(s) a.size();
    #define v() vector<ll>v
    #define PI 3.14159265
    //#define st string
    #define ss(a) sort(a.begin(),a.end())
    #define p 908197
    #define mod 1000000007
    ll mx(ll a[],ll n)
    {
        return *(max_element(a,a+n));
    }
    ll mi(ll a[],ll n)
    {
        return *(min_element(a,a+n));
    }
    ll power(ll x, ll y)
    {
        ll res = 1;	 // Initialize result
        x=x%mod;
        while (y > 0)
        {
            // If y is odd, multiply x with result
            if (y & 1)
                res = (res*x)%mod;

            // n must be even now
            y = y>>1; // y = y/2
            x = (x*x)%mod; // Change x to x^2
        }
        return res%mod;
    }

    void yes()
    {
        cout<<"YES\n";
    }
    void no()
    {
        cout<<"NO\n";
    }

    ll upperIndex(ll arr[], ll n, ll y)
    {
        ll l = 0, h = n;
        while (l <= h) {
            ll mid = (l + h) / 2;
            if (arr[mid] < y)
                l = mid + 1;
            else
                h = mid - 1;
        }
        return h;
    }
    void pa(ll a[],ll n)
    {
        f(i,n)
            cout<<a[i]<<" ";
        cout<<"\n";
    }
    void ga(ll a[],ll n) {
        f(i, n)
            cin>>a[i];
    }


    //long long int sum(ll i,ll j,ll l)
    //{

    //  return a[i][j]+a[i-l][j-l]-a[i][j-l]-a[i-l][j];
    //}
    //ll n,k,a,b;


    //ll pre[1000000];ll suff[1000000];
   /* vector<vector<ll>>a(300000);ll vis[300000];ll dist[300000];
    vector<ll>li;ll co=0;ll mxnod=-1;ll mxx=0;
    void dfs(ll st)
    {
         //cout<<st<<" ";
        //li.pb(st);
        f(i,a[st].size())
        {
            if(vis[a[st][i]]==0)
            {
                vis[a[st][i]]=1;co++;
              //  cout<<st<<" ";
                    dist[a[st][i]]=dist[st]+1;
                            if(dist[a[st][i]]>mxx)
                            {
                                mxx=dist[a[st][i]];
                                mxnod=a[st][i];
                            }
                    dfs(a[st][i]);

            }

        }


    }
    void dfs1(ll st)
    {
        //cout<<st<<" ";
        li.pb(st);
        f(i,a[st].size())
        {
            ll ch=a[st][i];

            if(dist[ch]==dist[st]-1)
            {
                //vis[a[st][i]]=1;
                //dist[a[st][i]]=dist[st]+1;
                dfs1(a[st][i]);

            }

        }


    }
    */
   //ll dp[][w]={0};


    int main() {
        ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        //   ll n,t,k;cin>>n>>t>>k;

    /*    ll t;cin>>t;
        while(t--)
        {




        }
        */



// Driver program

            int W ;
            int val[10002];

            int wt[10002];

            int h,n;
            cin>>h>>n;int maxi=-1;
            f(i,n)
            {
                cin>>wt[i]>>val[i];

                maxi=max(maxi,wt[i]);

            }
            W=h+maxi+2;
           // cout << unboundedKnapsack(W, n, val, wt);
ll dp[300000];
f(i,300000) {
    dp[i] = 100000000;
}

dp[0]=0;
        for (int i=1; i<=W; i++)
            for (int j=0; j<n; j++)
                if (wt[j] <= i)
                    dp[i] = min(dp[i], dp[i-wt[j]]+val[j]);
ll ans=100000000;
for(ll i=h;i<=W;i++)
{
    ans=min(ans,dp[i]);
}
cout<<ans;
    /*f(j,20)
    {
        cout<<sa1[j]<<" ";
    }
    cout<<"\n";
    */

      /*  ll n;cin>>n;
        ll a[n];
        f(i,n)
        {
            cin>>a[i];
        }

        */

    }

Measured memory_bytes: 1408