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