#include <bits/stdc++.h> using namespace std; int w[1005] , v[1005] , f[1005]; 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; }