#include <iostream>
using namespace std;
const int maxn=1000000000;
int main(){
    int n,m,a,b;
    while(cin>>n>>m){
        int ans=maxn;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            ans=min((n/a+(n%a?1:0))*b,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}