#include <iostream> #include <vector> using namespace std; int main(){ int n, c; while(cin >> c >> n){ int i(0), j, p, v, maxv(0); vector<int> dp(c+1); for (; i < n && cin >> p >> v; ++i) for (j = c; j >= p; --j) dp[j] = max(dp[j], v + dp[j - p]); cout << dp[c] << endl; } return 0; }