#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]; 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=m;j>=0;j--) { if(j>=f[i].w) { dp[j]=max(dp[j-f[i].w]+f[i].c,dp[j]); } } } cout<<dp[m]; return 0; }