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

#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    int n,h;
    cin>>h>>n;
    
    vector<int> a(n),b(n),dp(h+1,1e9);
    rep(i,n) cin>>a[i]>>b[i];
    
    dp[0]=0;
    rep(i,n)rep(j,h+1)dp[min(j+a[i],h)]=min(dp[min(j+a[i],h)],dp[j]+b[i]);
    cout<<dp[h];
    return 0;
}
