#include <bits/stdc++.h>
using namespace std;
int ans=0,n,m,v;
int w[40],c[40],f[40][200+10];
int main() {
cin>>v>>n;
for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
for(int k=0;k<=j/c[i];k++){
f[i][j]=max(f[i][j],f[i-1][j-k*c[i]]+k*w[i]);
}
}
}
cout<<"max="<<f[n][v]<<endl;
return 0;
}