#include<bits/stdc++.h> using namespace std; int m,n,c[1001],w[1001],dp[1001]; 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=c[i];j<=m;j++) dp[j]=max(dp[j],dp[j-c[i]]+w[i]); cout<<dp[m]; }