#include<bits/stdc++.h> using namespace std; int main() { int n,m,w[630]={},v[630]={},dp[55][605]={}; cin>>n>>m; for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[m][n]; return 0; }