#include<iostream> #include<cstdio> using namespace std; int w[20],v[20],f[20]; int main() { int m,n; scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]); for(int i=1;i<=n;i++) { for(int j=m;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0; }