#include<bits/stdc++.h> using namespace std; long long m,n,ans=0; struct st { long long c,w; }f[1097]; long long d[1097][1097]; int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>f[i].w>>f[i].c; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(j>=f[i].c) { d[i][j]=max(d[i-1][j-f[i].w]+f[i].c,d[i-1][j]); } else { d[i][j]=d[i-1][j]; } } } cout<<d[n][m]; return 0; }