#include <cmath> #include <cstring> #include <string.h> #include <queue> #include <stack> #include <map> using namespace std; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; int n,m; int w[N],v[N],dp[205]; int main(){ cin >> m >> n; for(int i=1; i<=n; i++) cin >> w[i] >> v[i]; for(int i= 1; i<=n; i++){ for(int j=m; j>=w[i]; j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout << dp[m]; }