#include <bits/stdc++.h> using namespace std; const int maxm=210,maxn=31; int m,n; int w[maxn],c[maxn]; int f[maxn][maxm]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(j<w[i]) f[i][j]=f[i-1][j]; else if(f[i-1][j]>f[i][j-w[i]]+c[i]) f[i][j]=f[i-1][j]; else f[i][j]=f[i][j-w[i]]+c[i]; printf("max=%d",f[n][m]); return 0; }