#include<bits/stdc++.h> using namespace std; int w[210],c[210]; int dp[40][210]; int main(){ int m,n; 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=0;j<=m;j++){ if(j>=c[i]){ dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]); }else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[n][m]; return 0; }