#include<bits/stdc++.h> using namespace std; int m,n,w[500],v[500],f[500][500]; 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=1;b<=m;b++) { if(b>=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; }