#include <bits/stdc++.h> using namespace std; int f[10001]; int main() { int m, n, w, c; cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> w >> c; for (int j = m; j >= w; j--) f[j] = max(f[j], f[j - w] + c); } cout << f[m] << endl; return 0; }