#include<iostream> using namespace std; const int N = 60, M = 450; int m, n, f[M], v[N], w[N]; int main(){ cin >> m >> n; for(int i = 1; i <= n; i++){ cin >> w[i] >> v[i]; } for(int i = 1; i <= n; i++){ for(int j = w[i]; j <= m; j++){ f[j] = max(f[j], f[j-w[i]] + v[i]); } } } cout << f[m]; return 0; }