dp

#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;
}