#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 5; int dp[2][N], w[N], v[N]; int main() { int n, m; cin >> m >> n; for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { dp[i & 1][j] = max(dp[i & 1][j], dp[i - 1 & 1][j]); if (j > w[i]) dp[i & 1][j] = max(dp[i & 1][j], dp[i - 1 & 1][j - w[i]] + v[i]); } cout << dp[n & 1][m] << endl; return 0; }