include <iostream>

using namespace std; int main() { int w,n; const int a=-1; cin>>w>>n; int h[n][2],s[w+1]; for(int i=0;i<n;i++) { for(int j=0;j<2;j++) { cin>>h[i][j]; } } s[0]=0; for(int j=1;j<=w;j++) { s[j]=a; } for(int i=0;i<n;i++) { for(int j=h[i][0];j<=w;j++) { if(s[j-h[i][0]]!=a and s[j]<s[j-h[i][0]]+h[i][1]) { s[j]=s[j-h[i][0]]+h[i][1]; } } } int maks=0; for(int i=1;i<=w;i++) { maks=max(maks,s[i]); } cout<<maks; }