#include<bits/stdc++.h> using namespace std; int m,n,w[100],v[100],f[100][100]; int main() { cin>>m>>n; for(int a=1;a<=n;a++) cin>>w[a]>>v[a]; for(int a=1;a<=n;a++) { for(int b=m;b>=1;b--) { if(m>=w[a]) f[a][b]=max(f[a][b],f[a][b-w[a]]+v[a]); f[a+1][b]=f[a][b]; } } cout<<f[n][m]; return 0; }