#include<bits/stdc++.h>
using namespace std;
long long m,n;
long long tim[10100];
long long v[10100];
long long dp[10000010];
int main(){
cin>>m>>n;
for(int t=1;t<=n;t++){
scanf("%lld%lld",&tim[t],&v[t]);
}
for(int t=1;t<=n;t++){
for(int i=m;i>=0;i--){
dp[i]=dp[i];
long long h=i/tim[t];
if(h!=0)
dp[i]=max(dp[i],dp[i-h*tim[t]]+v[t]*h);
}
}
printf("%lld",dp[m]);
return 0;
}
