#include<bits/stdc++.h> using namespace std; const int N=1005,M=105; int f[M][N],w[M],v[M]; int main(){ int m,t; cin>>t>>m; for(int i=1;i<=m;i++)cin>>v[i]>>w[i]; for(int i=1;i<=m;i++){ for(int j=1;j<=t;j++){ f[i][j]=f[i-1][j]; if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[m][t]; return 0; }