AC

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

int N, m;
cin >> N >> m;

vector<int> v(m), p(m);
for (int i = 0; i < m; ++i) {
    cin >> v[i] >> p[i];
}

vector<int> dp(N + 1, 0);

for (int i = 0; i < m; ++i) {
    int cost = v[i];
    int value = v[i] * p[i];
    for (int j = N; j >= cost; --j) {
        dp[j] = max(dp[j], dp[j - cost] + value);
    }
}

cout << dp[N] << endl;

return 0;

}