#include<iostream> using namespace std; const int N = 1e3 + 10; int m, n, f[N][N], w[N], c[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 = m; j >= 0; j--){ f[i][j] = f[i-1][j]; if(j >= w[i]){ f[i][j] = max(f[i][j], f[i-1][j-w[i]] + c[i]); } } } cout << f[n][m]; }