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