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