#include<iostream> #include<cstdio> using namespace std; int w[20] , v[20] , f[20]; int main() { int m , n; 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 = m;j >= w[i];j--) f[j] = max(f[j] , f[j - w[i]] + v[i]); cout << f[m]; return 0; }