#include<iostream> using namespace std; int w[1001],c[1001],dp[1001][1001]; int m,n; int main(){ 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; }