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