#include<bits/stdc++.h> using namespace std; int n,m,v[10001],w[10001],dp[10001][10001]; 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 k=m;k>0;k--) { if (w[i]<=k) dp[i][k]=max(dp[i-1][k],dp[i-1][k-w[i]]+v[i]); else dp[i][k]=dp[i-1][k]; } } cout<<dp[n][m]<<endl; return 0; }