#include "bits/stdc++.h"
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define rep(i,b) for(ll i=0;i<b;i++)

using namespace std;

int main(){
    ll h,n,a,b;
    cin>>h>>n;
    vl dp(10005,10e9);
    dp[h]=0;
    rep(i,n){
        cin>>a>>b;
        for(ll j=h;j;j--) dp[max(0LL, j - a)] = min(dp[max(0LL, j - a)], dp[j] + b);
    }
    cout<<dp[0]<<endl;
}