#include <bits/stdc++.h>
using namespace std;
int f[41][201],w[41],c[41];
int n,m,v;
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];
return 0;
}