#include #include #include using namespace std;

int n, m; int v[25], p[25]; int f[30005];

int main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> v[i] >> p[i]; p[i] *= v[i]; }

for (int i = 1; i <= m; ++i) {
    for (int j = n; j >= v[i]; --j) {
        f[j] = max(f[j], f[j - v[i]] + p[i]);
    }
}

cout << f[n] << endl;

return 0;

}