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