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