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