#include<iostream> #include<algorithm> using namespace std; int w[1010],c[1010],dp[1010][1010]; int main(){ int n,m; cin>>m>>n; for(int i = 1; i <= n; i++){ cin>>w[i]>>c[i]; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(j >= w[i]){ dp[i][j] = max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]); }else{ dp[i][j] = dp[i-1][j]; } } } cout<<dp[n][m]; return 0; }