#include <bits/stdc++.h> using namespace std; int a[20005],p[105],dp[105][20005]; int main(){ int c,n; cin>>c>>n; for(int i=1;i<=n;i++){ cin>>a[i]>>p[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=c;j++){ if(a[i]<=j){ dp[i][j]=max(dp[i-1][j],p[i]+dp[i-1][j-a[i]]); }else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[n][c]<<endl; return 0; }