#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int MAXN = 1e3 + 1e2; int w[MAXN]; int v[MAXN]; int f[MAXN]; int m, n; int main() { scanf("%d %d", &m, &n); for (int i = 1;i <= n;i++) scanf(" %d %d", &w[i], &v[i]); for (int i = 1;i <= n;i++) for (int j = m;j >= w[i];j--) f[j] = max(f[j - 1], f[j - w[i]] + v[i]); printf("%d", f[m]); return 0; }