#include <bits/stdc++.h> using namespace std; const int maxm=201,maxn = 31; int m,n; int w[maxn],c[maxn]; int f[maxn][maxm]; int main() { 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++) if(v<w[i]) f[i][v]=f[i-1][v]; else if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v]; else f[i][v]=f[i][v-w[i]]+c[i]; cout<<"max="<<f[n][m]<<endl; return 0; }