#include<bits/stdc++.h> using namespace std; int m,n,w[16384],c[16384],dp[16384],ans; int main(){ cin>>m>>n; for(int i=1;i<=n;i++)cin>>w[i]>>c[i]; for(int i=1;i<=n;i++)for(int j=c[i];j<=m;j++){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]),ans=max(dp[j],ans); }cout<<ans; return 0; }