#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--) if (f[j - w[i]] + v[i] > f[j]) f[j] = f[j - w[i]] + v[i]; printf("%d", f[m]); return 0; }